Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Теорема Дейкстры



Читайте также:
  1. Алгоритм Дейкстры
  2. Алгоритмические задачи поиска в графах: задачи Прима-Краскала, Дейкстры, Форда-Фалкерсона.
  3. Великая теорема Ферма
  4. Теорема (Правило вершин). Оптимальное решение задачи линейного программирования достигается в одной из вершин области.
  5. ТЕОРЕМА БЕЛЛА
  6. Теорема Белла: часть 2

Алгоритм Дейкстры корректен, дает правильный результат для любого графа.

В качестве док-ва можно рассмотреть простые соображения – методом от противного.

Если бы из А в X существовал более короткий путь, то он обязательно отражался бы в одной из строчек столбца X0, т.к. путь в X рассматривается из всех вершин. Т.о., наличие непроверенного короткого пути в X требует наличие таких же непроверенных путей для всех вершин этого пути, что в принципе невозможно Ч.Т.Д.

Существует удобный алгоритм Флойда-Уоршела Для решения задачи Дейкстры.

, где - матрица кратчайших путей между вершинами и .

Вычисление по этой формуле в цикле по i, по j и внутри цикла k.

Этот алгоритм является следствием алгоритма Дейкстры, но находит расстояние между всеми вершинами. В результате он гораздо менее эффективен с точки зрения затраты времени на выполнение.


Дата добавления: 2015-07-11; просмотров: 345 | Нарушение авторских прав






mybiblioteka.su - 2015-2024 год. (0.006 сек.)