Алгоритм дейкстры для графа онлайн. Графы. Нахождение кратчайшего расстояния между двумя вершинами с помощью алгоритма Дейкстры. Построение дерева кратчайших путей
5.4.3. Задача о кратчайшем пути и алгоритм Дейкстры ее решения
Пусть задан орграф G
(V
,
E
), каждой дуге
которого поставлено в соответствие
число
,
называемое длиной дуги
.
Определение. Длиной пути называется сумма длин дуг, составляющих этот путь. Задача о кратчайшем пути ставится так.
Вариант 1. Найти длины кратчайших путей (путей минимальной длины) и сами пути от фиксированной вершины s до всех остальных вершин графа.
Вариант 2. Найти длины кратчайших путей и сами пути между всеми парами вершин данного графа.
Если в графе имеются дуги отрицательной
длины, задача может не иметь решений
(потеряет смысл). Это происходит из-за
того, что в графе может присутствовать
контур отрицательной длины. Наличие
контуров отрицательной длины означает,
что длину пути можно сделать равной
.
А если контуров отрицательной длины
нет, то кратчайшие пути существуют и
любой кратчайший путь – это простая
цепь.
Заметим, что если кратчайший путь существует, то любой его подпуть – это тоже кратчайший путь между соответствующими вершинами.
Алгоритм Дейкстры решения задачи о кратчайшем пути.
Алгоритм работает с дугами положительной длины и определяет кратчайшие пути от фиксированной вершины s до всех остальных вершин графа. Обозначим эти вершины v 1 , v 2 ,…, v n .
Определение. Назовем вершину u лежащей ближе к вершине s , чем вершина v , если длина кратчайшего пути от s до u меньше длины кратчайшего пути от s до v . Будем говорить, что вершины u и v равноудалены от вершины s , если длины кратчайших путей от s до u и от s до v совпадают.
Алгоритм Дейкстры последовательно упорядочивает вершины графа в смысле близости к вершине s и основан на следующих базовых принципах.
Если длины дуг – положительные числа, то
ближайшая к s вершина – она сама. Длина кратчайшего пути от s до s равна 0;
ближайшая к s вершина, отличная от s , лежит от s на расстоянии одной дуги самой короткой из всех дуг, выходящих из вершины s ;
любая промежуточная вершина кратчайшего пути от s до некоторой вершины v лежит ближе к s , чем конечная вершина v ;
кратчайший путь до очередной упорядоченной вершины может проходить только через уже упорядоченные вершины.
Пусть алгоритм уже упорядочил вершины
v
1 ,
v
2 …
v
k
.
Обозначим через
,
длину кратчайшего пути до вершины v
i
.
Рассмотрим все дуги исходного графа,
которые начинаются в одной из вершин
множества
и оканчиваются в еще неупорядоченных
вершинах. Для каждой такой дуги, например
,
вычислим сумму
.
Эта сумма равна длине пути из s
в y
, в котором вершина
v
i
есть предпоследняя вершина, а путь из
s
в v
i
– кратчайший из всех путей, соединяющих
s
и v
i
.
Этим самым определены длины всех путей
из s
в еще не упорядоченные
вершины, в которых промежуточными
вершинами являются только вершины из
числа k
ближайших к
s
. Пусть кратчайший
из этих путей оканчивается на вершине
w
. Тогда w
и есть
по близости к s
вершина.
Технически действия по алгоритму
Дейкстры осуществляются при помощи
аппарата меток вершин. Метка вершины v
обозначается как
.
Всякая метка – это число, равное длине
некоторого пути от s
до v
. Метки делятся
на временные и постоянные. На каждом
шаге только одна метка становиться
постоянной. Это означает, что ее значение
равно длине кратчайшего пути до
соответствующей вершины, а сама эта
вершина упорядочивается. Номер очередной
упорядоченной вершины обозначим буквой
р
.
Описание алгоритма .
Шаг 1.
(Начальная установка)
.
Положить
и считать эту метку постоянной. Положить
,
и считать эти метки временными.
Положить
.
Шаг 2. (Общий шаг). Он повторяется n раз, пока не будут упорядочены все вершины графа.
Пересчитать временную метку
всякой неупорядоченной вершины v
i
,
в которую входит дуга, выходящая из
вершины р,
по правилу
Выбрать вершину с минимальной временной меткой. Если таких вершин несколько, выбрать любую.
Пусть w
-
вершина
с минимальной временной меткой. Считать
метку
постоянной и положить
.
Шаги алгоритма Дейкстры удобно оформлять в таблице, каждый столбец которой соответствует вершине графа. Строки таблицы соответствуют повторению общего шага.
Пример
.
Для графа на рис. 4. найти
кратчайшие пути от вершин
до всех остальных вершин графа. Ребра
означают две разнонаправленные дуги
одинаковой длины.
Решение. В табл. 1 записаны метки вершин на каждом шаге. Постоянные метки помечены знаком «+». Подробно опишем, как вычисляются метки вершин.
Из вершины 1 выходят дуги в вершины 2, 5, 6. Пересчитываем метки этих вершин и заполним вторую строку таблицы.
Метка вершины 6 становиться постоянной,
.
Из вершины 6 выходят дуги в еще неупорядоченные вершины 2, 5, 8, 9. Пересчитываем их временные метки
Заполняем 3 строку таблицы. Минимальная
из временных меток равна 3 (метка вершины
9),
.
Из вершины 9 выходят дуги в еще неупорядоченные вершины 5, 8, 11, 12. Тогда
Заполняем четвертую строку таблицы. В этой строке две вершины 2 и 12 имеют минимальные временные метки, равные 4. Сначала упорядочим, например, вершину 2. Тогда на следующем шаге будет упорядочена вершина 12.
Таблица 1
.
Из вершины 2 выходят дуги в еще неупорядоченные вершины 3, 4, 5. Пересчитываем временные метки этих вершин
Заполняем 5 строку таблицы. Минимальная
из временных меток равна 4 (метка вершины
12),
.
Заполняем 6 строку таблицы. Минимальная
из временных меток равна 5 (метка вершины
5),
.
Заполняем 7 строку таблицы. Становиться
постоянной метка вершины 8 (она равна
5),
.
Вершина 11 упорядочивается.
Из вершины 11 выходят дуги в неупорядоченные вершины 7, 10. Пересчитываем временные метки этих вершин
Вершина 4 получает постоянную метку.
Из вершины 4 выходят дуги в неупорядоченные вершины 3, 7. Пересчитываем временные метки
Упорядочиваем вершину 3.
Заполняем 12 строку таблицы. На этом шаге упорядочиваем последнюю неупорядоченную вершину 10.
Построение дерева кратчайших путей.
Дерево кратчайших путей – это ориентированное дерево с корнем в вершине S . Все пути в этом дереве – кратчайшие для данного графа.
Дерево кратчайших путей строится по таблице, в него включаются вершина за вершиной в том порядке, в котором они получали постоянные метки. Первым в дерево включается корень – вершина S .
Построим дерево кратчайших путей для нашего примера.
Сначала включаем в дерево корень –
вершину 1. Затем в дерево включается
дуга (1,6). Следующей была упорядочена
вершина 9, длина кратчайшего пути до
которой равна 3. Первый раз число 3
появилось в третьей строке, которая
заполнялась при
.
Следовательно, вершина 6 – предпоследняя
вершина кратчайшего пути до вершины 9.
Включаем в дерево дугу (6,9) длины 1.
Затем была упорядочена вершина 2 с длиной
кратчайшего пути, равной 4. Это число
первый раз появилось в третьей строке,
которая заполнялась при
.
Следовательно, кратчайший путь во вторую
вершину проходит по дуге (6,2). Включаем
в дерево дугу (6,2) длины 2.
Далее была упорядочена вершина 12,
.
Первый раз число 4 появляется в четвертой
строке, которая заполнялась при
.
В дерево включается дуга (9,12) длины 1.
Полное дерево кратчайших путей показано
на рис. 5.
Алгоритм Дейкстры может ошибаться, если в графе есть дуги отрицательной длины. Так, отыскивая кратчайшие пути от вершины s =1 для графа на рис. 6, алгоритм сначала упорядочит вершину 3, затем вершину 2 и закончит работу. При этом этот кратчайший путь до вершины 3, с точки зрения алгоритма Дейкстры, это дуга (1,3) длины 3.
На самом деле, кратчайший путь до вершины 3 состоит из дуг (1,2) и (2,3), длина этого пути равна 5+(-3)=2.
Из-за наличия дуги (2,3) отрицательной длины –3 оказались нарушенными следующие базовые принципы:
ближайшая к s вершина лежит от нее на расстоянии двух дуг, а не одной;
промежуточная вершина кратчайшего пути 1-2-3 (вершина 2) лежит дальше от вершины 1 (на расстоянии 5), чем конечная вершина пути 3.
Следовательно, присутствие дуг отрицательной длины усложняет решение задачи о кратчайшем пути и требует использования более сложных алгоритмов, нежели алгоритм Дейкстры.
Алгоритм Дейкстры (англ. Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Кружками обозначены вершины, линиями - пути между ними (рёбра графа). В кружках обозначены номера вершин, над рёбрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.
Первый шаг . Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.
Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме значения метки вершины 1 и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.
Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.
Второй шаг . Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещённых вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.
Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.
Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а это меньше 17, поэтому метка не меняется.
Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<, устанавливаем метку вершины 4 равной 22.
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещённую.
Третий шаг . Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:
Дальнейшие шаги . Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.
Завершение выполнения алгоритма . Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины. В данном примере все вершины зачёркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться незачёркнутыми, если до них нельзя добраться, т. е. если граф несвязный. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.
Реализация алгоритма на различных языках программирования:
C++
#include "stdafx.h" #includePascal
program DijkstraAlgorithm; uses crt; const V=6; inf=100000; type vektor=array of integer; var start: integer; const GR: array of integer=((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); {алгоритм Дейкстры} procedure Dijkstra(GR: array of integer; st: integer); var count, index, i, u, m, min: integer; distance: vektor; visited: array of boolean; begin m:=st; for i:=1 to V do begin distance[i]:=inf; visited[i]:=false; end; distance:=0; for count:=1 to V-1 do begin min:=inf; for i:=1 to V do if (not visited[i]) and (distance[i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) and (distance[u]<>inf) and (distance[u]+GRJava
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Solution { private static int INF = Integer.MAX_VALUE / 2; private int n; //количество вершин в орграфе private int m; //количествое дуг в орграфе private ArrayListЕщё один вариант:
Import java.io.*;
import java.util.*;
public class Dijkstra {
private static final Graph.Edge GRAPH = {
new Graph.Edge("a", "b", 7),
new Graph.Edge("a", "c", 9),
new Graph.Edge("a", "f", 14),
new Graph.Edge("b", "c", 10),
new Graph.Edge("b", "d", 15),
new Graph.Edge("c", "d", 11),
new Graph.Edge("c", "f", 2),
new Graph.Edge("d", "e", 6),
new Graph.Edge("e", "f", 9),
};
private static final String START = "a";
private static final String END = "e";
public static void main(String args) {
Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.printPath(END);
//g.printAllPaths();
}
}
class Graph {
private final Map
C
#includePHP
$edge, "cost" => $edge); $neighbours[$edge] = array("end" => $edge, "cost" => $edge); } $vertices = array_unique($vertices); foreach ($vertices as $vertex) { $dist[$vertex] = INF; $previous[$vertex] = NULL; } $dist[$source] = 0; $Q = $vertices; while (count($Q) > 0) { // TODO - Find faster way to get minimum $min = INF; foreach ($Q as $vertex){ if ($dist[$vertex] < $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";
Python
from collections import namedtuple, queue
from pprint import pprint as pp
inf = float("inf")
Edge = namedtuple("Edge", "start, end, cost")
class Graph():
def __init__(self, edges):
self.edges = edges2 =
self.vertices = set(sum(( for e in edges2), ))
def dijkstra(self, source, dest):
assert source in self.vertices
dist = {vertex: inf for vertex in self.vertices}
previous = {vertex: None for vertex in self.vertices}
dist = 0
q = self.vertices.copy()
neighbours = {vertex: set() for vertex in self.vertices}
for start, end, cost in self.edges:
neighbours.add((end, cost))
#pp(neighbours)
while q:
u = min(q, key=lambda vertex: dist)
q.remove(u)
if dist[u] == inf or u == dest:
break
for v, cost in neighbours[u]:
alt = dist[u] + cost
if alt < dist[v]: # Relax (u,v,a)
dist[v] = alt
previous[v] = u
#pp(previous)
s, u = deque(), dest
while previous[u]:
s.pushleft(u)
u = previous[u]
s.pushleft(u)
return s
graph = Graph([("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10),
("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6),
("e", "f", 9)])
pp(graph.dijkstra("a", "e"))
Output:
["a", "c", "d", "e"]
Для начала рассмотрим алгоритм Фалкерсона (графический способ упорядочивания элементов):
- 1. Найти вершины графа, в которые не входит не одна дуга. Они образуют первую группу. Пронумеровать вершины группы в произвольном порядке.
- 2. Вычеркнуть все пронумерованные вершины и дуги, из них исходящие. В получившемся графе найдется, по крайней мере, одна вершина, в которую не входит ни одна дуга. Этой вершине, входящей во вторую группу, присвоить очередной номер, и т. д. Второй шаг повторять до тех пор, пока не будут упорядочены все вершины.
Теперь рассмотрим алгоритм нахождения кратчайшего пути между двумя заданными вершинами в ориентированном графе. Пусть G = {S, U, ? } - ориентированный граф со взвешенными дугами. Обозначим s-вершину - начало пути и t-вершину - конец пути.
Алгоритм Дейкстры содержит одно ограничение - веса дуг должны быть положительными. Сам алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути, на втором строится сам путь от вершины s к вершине t.
Этап 1. Нахождение кратчайшего пути.
Шаг 1. Присвоение вершинам начальных меток.
Полагаем d(s)=0* и считаем эту метку постоянной (постоянные метки помечаются сверху звёздочкой). Для остальных вершин x i S, x i ?s полагаем d(x i) = ? и считаем эти метки верными. Пусть x” = s, x” - обозначение текущей вершины.
Шаг 2. Изменение меток.
Для каждой вершины x i с временной меткой, непосредственно следующей за вершиной x”, меняем ее метку в соответствии со следующим правилом:
d нов. (x i) = min{d стар. (x i), d(x”)+щ(x”, x i)}.(1. 6. 1)
Шаг 3. Превращение метки из временной в постоянную.
Из всех вершин с временными метками выбираем вершину x j * с наименьшим значением метки
d(x j *) = min {d(x j) / x j S, d(x j) - временная}. (1. 6. 2)
Превращаем эту метку в постоянную и полагаем x” = x j *.
Шаг 4. Проверка на завершение первого этапа.
Если x” = t, то d(x”) - длина кратчайшего пути от s до t. В противном случае происходит возвращение ко второму шагу.
Этап 2. Построение кратчайшего пути.
Шаг 5. Последовательный поиск дуг кратчайшего пути.
Среди вершин, непосредственно предшествующих вершине x” c постоянными метками, находим вершину x i , удовлетворяющую соотношению
d(x”) = d(x i) + щ(x i , x”).(1. 6. 3)
Включаем дугу (x i , x”) в искомый путь и полагаем x” = x i .
Шаг 6. Проверка на завершение второго этапа.
Если x” = s, то кратчайший путь найден - его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу.
Пример 8: Задана весовая матрица? графа G. Найти минимальный путь из вершины x 1 в вершину x6 по алгоритму Дейкстры.
На рисунке 1. 11 изображён сам граф по данной матрице весов. Поскольку на данном графе есть цикл между вершинами x 2 , x 3 и x 5 , то вершины графа нельзя упорядочить по алгоритму Фалкерсона. На рисунке графа временные и постоянные метки указаны над соответствующей вершиной. Итак, распишем подробно работу алгоритма Дейкстры по шагам.
Шаг 1. Полагаем d(x 1) = 0*, x” = x 1 , d(x 2) = d(x 3) = d(x 4) = d(x 5) = d(x 6) = ?.
1-ая итерация.
Шаг 2. Множество вершин, непосредственно следующих за x” = x1 со временными метками S” = {x 2 , x 4 , x 5 }. Пересчитываем временные метки вершин: d(x 2) = min{?, 0*, + 9} = 9, d(x 4) = min{?, 0* + 6} = 6, d(x 5) = min{?, 0* + 11} = 11.
Шаг 3. Одна из временных меток превращается в постоянную min{9, ?, 6, 11, ?} = 6* = d(x 4), x” = x 4 .
Шаг 4. x” = x 4 ? t = x 6 , происходит возвращение на второй шаг.
2-ая итерация.
Шаг 2. S” = {x 2 , x 3 , x 5 }, d(x 2) = min{9, 6* + 5} = 9, d(x 3) = min {?, 6* + 7} = 13, d(x 5) = min{11, 6* + 6} = 11.
Шаг 3. min{d(x 2), d(x 3), d(x 5), d(x 6)} = min{9, 13, 11, ?} = 9* = d(x 2), x” = x 2 .
Шаг 4. x 2 ? x 6 , возвращение на второй шаг.
3-я итерация.
Шаг 2. S” ={x 3 }, d(x 3) = min{13, 9* + 8} = 13.
Шаг 3. min{d(x 3), d(x 5), d(x 6)} = min{31, 11, ?} = 11* = d(x 5), x” = x 5 .
Шаг 4. x 5 ? x 6 , возвращение на второй шаг.
4-ая итерация.
Шаг 2. S”={x 6 }, d(x 6) = min{?, 11* + 4} = 15.
Шаг 3. min {d(x 3), d(x 6)} = min{13, 15} = 13* = d(x 3), x” = x 3 .
Шаг 4. x 3 ? x 6 , возвращение на второй шаг.
5-ая итерация.
Шаг 2. S” = {x 6 }, d(x 6) = min{15, 13* + 9} = 15.
Шаг 3. min{d(x 6) } = min{15} = 15*, x” = x 6 .
Шаг 4. x 6 = t = x 6 , конец первого этапа.
Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x 6 с постоянными метками S” = {x 3 , x 5 }. Проверим для этих двух вершин выполнение равенства d нов. (x i) = min{d стар. (x i), d(x”) + щ(x”, x i)}:
d(x”) = 15 = 11* + 4 = d(x 5) + щ(x 5 , x 6),
d(x”) = 15 ? 13* + 9 = d(x 3) + щ(x 3 , x 6).
Включаем дугу (x 5 , x 6) в кратчайший путь. x” = x 5 .
Шаг 6. x” ? s = x 1 , возвращение на пятый шаг.
2-ая итерация.
Шаг 5. S” = {x 1 , x 4 }.
d(x”) = 11 = 0* + 11 = d(x 1) + щ(x 1 , x 5),
d(x”) = 11 ? 6* + 6 = d(x 4) + щ(x 4 , x 5).
Включаем дугу (x 1 , x 5) в кратчайший путь. x” = x 1 .
Шаг 6. x” = s = x 1 , завершение второго этапа.
Итак, кратчайший путь от вершины x 1 до вершины x 6 построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг: м = (x 1 , x 5) - (x 5 , x 6).
Дан ориентированный или неориентированный взвешенный граф с вершинами и рёбрами. Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина . Требуется найти длины кратчайших путей из вершины во все остальные вершины, а также предоставить способ вывода самих кратчайших путей.
Эта задача называется "задачей о кратчайших путях с единственным источником" (single-source shortest paths problem).
Алгоритм
Здесь описывается алгоритм, который предложил голландский исследователь Дейкстра (Dijkstra) в 1959 г.
Заведём массив , в котором для каждой вершины будем хранить текущую длину кратчайшего пути из в . Изначально , а для всех остальных вершин эта длина равна бесконечности (при реализации на компьютере обычно в качестве бесконечности выбирают просто достаточно большое число, заведомо большее возможной длины пути):
Кроме того, для каждой вершины будем хранить, помечена она ещё или нет, т.е. заведём булевский массив . Изначально все вершины не помечены, т.е.
Сам алгоритм Дейкстры состоит из итераций . На очередной итерации выбирается вершина с наименьшей величиной среди ещё не помеченных, т.е.:
(Понятно, что на первой итерации выбрана будет стартовая вершина .)
Выбранная таким образом вершина отмечается помеченной. Далее, на текущей итерации, из вершины производятся релаксации : просматриваются все рёбра , исходящие из вершины , и для каждой такой вершины алгоритм пытается улучшить значение . Пусть длина текущего ребра равна , тогда в виде кода релаксация выглядит как:
На этом текущая итерация заканчивается, алгоритм переходит к следующей итерации (снова выбирается вершина с наименьшей величиной , из неё производятся релаксации, и т.д.). При этом в конце концов, после итераций, все вершины графа станут помеченными, и алгоритм свою работу завершает. Утверждается, что найденные значения и есть искомые длины кратчайших путей из в .
Стоит заметить, что, если не все вершины графа достижимы из вершины , то значения для них так и останутся бесконечными. Понятно, что несколько последних итераций алгоритма будут как раз выбирать эти вершины, но никакой полезной работы производить эти итерации не будут (поскольку бесконечное расстояние не сможет прорелаксировать другие, даже тоже бесконечные расстояния). Поэтому алгоритм можно сразу останавливать, как только в качестве выбранной вершины берётся вершина с бесконечным расстоянием.
Восстановление путей . Разумеется, обычно нужно знать не только длины кратчайших путей, но и получить сами пути. Покажем, как сохранить информацию, достаточную для последующего восстановления кратчайшего пути из до любой вершины. Для этого достаточно так называемого массива предков : массива , в котором для каждой вершины хранится номер вершины , являющейся предпоследней в кратчайшем пути до вершины . Здесь используется тот факт, что если мы возьмём кратчайший путь до какой-то вершины , а затем удалим из этого пути последнюю вершину, то получится путь, оканчивающийся некоторой вершиной , и этот путь будет кратчайшим для вершины . Итак, если мы будем обладать этим массивом предков, то кратчайший путь можно будет восстановить по нему, просто каждый раз беря предка от текущей вершины, пока мы не придём в стартовую вершину — так мы получим искомый кратчайший путь, но записанный в обратном порядке. Итак, кратчайший путь до вершины равен:
Осталось понять, как строить этот массив предков. Однако это делается очень просто: при каждой успешной релаксации, т.е. когда из выбранной вершины происходит улучшение расстояния до некоторой вершины , мы записываем, что предком вершины является вершина :
Доказательство
Основное утверждение , на котором основана корректность алгоритма Дейкстры, следующее. Утверждается, что после того как какая-либо вершина становится помеченной, текущее расстояние до неё уже является кратчайшим, и, соответственно, больше меняться не будет.
Доказательство будем производить по индукции. Для первой итерации справедливость его очевидна — для вершины имеем , что и является длиной кратчайшего пути до неё. Пусть теперь это утверждение выполнено для всех предыдущих итераций, т.е. всех уже помеченных вершин; докажем, что оно не нарушается после выполнения текущей итерации. Пусть — вершина, выбранная на текущей итерации, т.е. вершина, которую алгоритм собирается пометить. Докажем, что действительно равно длине кратчайшего пути до неё (обозначим эту длину через ).
Рассмотрим кратчайший путь до вершины . Понятно, этот путь можно разбить на два пути: , состоящий только из помеченных вершин (как минимум стартовая вершина будет в этом пути), и остальная часть пути (она тоже может включать помеченные вершины, но начинается обязательно с непомеченной). Обозначим через первую вершину пути , а через — последнюю вершины пути .
Докажем сначала наше утверждение для вершины , т.е. докажем равенство . Однако это практически очевидно: ведь на одной из предыдущих итераций мы выбирали вершину и выполняли релаксацию из неё. Поскольку (в силу самого выбора вершины ) кратчайший путь до равен кратчайшему пути до плюс ребро , то при выполнении релаксации из величина действительно установится в требуемое значение.
Вследствие неотрицательности стоимостей рёбер длина кратчайшего пути (а она по только что доказанному равна ) не превосходит длины кратчайшего пути до вершины . Учитывая, что (ведь алгоритм Дейкстры не мог найти более короткого пути, чем это вообще возможно), в итоге получаем соотношения:
С другой стороны, поскольку и , и — вершины непомеченные, то так как на текущей итерации была выбрана именно вершина , а не вершина , то получаем другое неравенство:
Из этих двух неравенств заключаем равенство , а тогда из найденных до этого соотношений получаем и:
что и требовалось доказать.
Реализация
Итак, алгоритм Дейкстры представляет собой итераций, на каждой из которых выбирается непомеченная вершина с наименьшей величиной , эта вершина помечается, и затем просматриваются все рёбра, исходящие из данной вершины, и вдоль каждого ребра делается попытка улучшить значение на другом конце ребра.
Время работы алгоритма складывается из:
При простейшей реализации этих операций на поиск вершины будет затрачиваться операций, а на одну релаксацию — операций, и итоговая асимптотика алгоритма составляет:
Реализация :
const int INF = 1000000000 ; int main() { int n; ... чтение n ... vector < vector < pair< int ,int > > > g (n) ; ... чтение графа... int s = ...; // стартовая вершина vector< int > d (n, INF) , p (n) ; d[ s] = 0 ; vector< char > u (n) ; for (int i= 0 ; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }Здесь граф хранится в виде списков смежности: для каждой вершины список содержит список рёбер, исходящих из этой вершины, т.е. список пар >, где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.