Алгоритм Дейкстры
EW Dijkstra (1930-2002) предложил в 1959 г. алгоритм (называемый алгоритмом Дейкстры), который позволяет определить кратчайший путь между двумя вершинами a график связанный взвешенный. Алгоритм Дейкстры основан на следующем наблюдении: как только мы определяем кратчайший путь к вершине v, пути, идущие от v к каждой из ее смежных вершин, могут быть кратчайшими путями к каждой из этих соседних вершин. Алгоритм Дейкстры представляет собой алгоритм динамическое программирование прожорливый, он посещает все возможные решения.
Условия
- Нет отрицательной длины
- Дуга или край
- Конечное количество вершин
- Источник (и, кстати, цель), определенный
Алгоритм Дейкстры принимает на вход ориентированный граф, взвешенный положительными действительными числами, и исходную вершину. Это включает в себя постепенное построение подграфа, в котором различные вершины классифицируются в порядке возрастания их минимального расстояния от начальной вершины. Расстояние соответствует сумме весов взятых ребер.
Первоначально считаем, что расстояния от каждой вершины до начальной вершины бесконечны, за исключением начальной вершины, для которой расстояние равно 0. Начальным подграфом является пустое множество.
На каждой итерации за пределами подграфа выбирается вершина минимального расстояния и добавляется в подграф (она становится посещаемой вершиной). Затем мы обновляем расстояния соседних вершин добавленной (вершины отмечены). Обновление работает следующим образом: новое расстояние от соседней вершины является минимальным между существующее расстояние и полученный добавлением вес дуги между соседней вершиной и вершиной, прибавленный к расстоянию от добавленной вершины.
Продолжаем таким образом до тех пор, пока подграф не будет полностью завершен (или пока не будет выбрана вершина прибытия). Пример :
| расстояние | к А | до Б | до С | к Д | палец | к F | к G | в Н | имеют | к Д |
|---|---|---|---|---|---|---|---|---|---|---|
| Начальная стадия | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| А(0) | 85 | 217 | ∞ | 173 | ∞ | ∞ | ∞ | ∞ | ∞ | |
| Б(85В) | – | 217 | ∞ | 173 | 165 | ∞ | ∞ | ∞ | ∞ | |
| Ф(165Б) | – | 217 | ∞ | 173 | – | ∞ | ∞ | 415 | ∞ | |
| Е(173В) | – | 217 | ∞ | – | – | ∞ | ∞ | 415 | 675 | |
| С(217В) | – | – | ∞ | – | – | 403 | 320 | 415 | 675 | |
| Н(320ПРОТИВ) | – | – | 503 | – | – | 403 | – | 415 | ||
| Г(403ПРОТИВ) | – | – | 503 | – | – | – | – | 415 | 487 | |
| я(415Ф) | – | – | 503 | – | – | – | – | – | 487 | |
| Дж(487ЧАС) | – | – | 503 | – | – | – | – | – | – | |
| Д(503ЧАС) | – | – | – | – | – | – | – | – | – |
По практическим причинам разрешение алгоритма Дейкстры возвращает только вектор, содержащий посещенную вершину, список предшественников (уже проверенных вершин) и значения кратчайших путей ко всем остальным вершинам. Что соответствует текущей строке представленной таблицы. Используя левую колонку, мы можем создать дерево кратчайшие пути из вершины А во все вершины.
Начальная вершина — это кратчайший путь к самой себе. Затем мы вычисляем все пути размера 1, начинающиеся с этой вершины, чтобы проверить кратчайший. Таким образом, этот путь является кратчайшим путем из начальной вершины, потому что нет ребра с отрицательным весом. По индукции мы делаем вывод, что алгоритм всегда проверяет кратчайший путь.
d[0]=0, d[i]=бесконечность для любой вершины, кроме исходной
так долго как'есть вершина вне подграфа п
выбрать вершину в снаружи п на меньшем расстоянии д[а]
помещать в в п
за каждая вершина б снаружи п сосед в
d [b] = мин (d [b], d [a] + вес (a, b))
конец
конец
вернуться из
RU 
FR 
EN 
ES