Алгоритм Дейкстры

Дано: непyстой взвешенный гpаф G=(V,E) с неотрицательными весами ребер (дуг). Требуется найти кpатчайший пyть от s к t (st).

Инициализация:

1. всем веpшинам v_i пpиписывается метка - вещественное число: d(s)=0, d(v_i)=+ для всех v_is;

2. метки всех вершин, кроме s, считаются вр'еменными, метка s - постоянной;

3. вершина s объявляется текущей (c:=s);

4. все ребра (дуги) считаются непомеченными.

Основная часть:

1. для всех вершин u_j, инцидентных текущей вершине c, метки которых являются временными, пересчитываем эти метки по формуле: d(u_j):=min{d(u_j), d(c)+Weight(c,u_j)} (*), где (c,u_j) - ребро (дуга), соединяющая вершины c и u_j, а Weight(c,u_j) - ее вес; при наличии кратных ребер выбирается ребро с минимальным весом;

2. если метки всех вершин являются постоянными либо равны , то путь не существует; ВЫХОД("нет решения");

3. иначе находим среди вершин с временными метками (среди всех таких вершин, а не только тех, чьи метки изменились в результате последнего выполнения шага (1)!) вершину x с минимальной меткой, объявляем ее метку постоянной, помечаем ребро (дугу) (c',x), такое, что d(x) = d(c')+Weight(c',x), где c'=с либо c' - вершина, бывшая текущей на одном из предыдущих шагов (c'=с, если на шаге (1) при u_j=x реализовалась вторая часть формулы (*)), и делаем эту вершину текущей (c:=x);

4. если c=t, то найден путь длины d(t), который можно восстановить следующим образом: это тот путь между s и t, который состоит только из помеченных на шаге (3) ребер (дуг) (можно доказать, что он существует и единственен); ВЫХОД("решение найдено");

5. иначе переходим на шаг (1).

~

Алгоритм Дейкстры не всегда находит правильное решение в случае произвольных весов ребер (дуг) графа. Например, для орграфа, изображенного на рисунке, алгоритм Дейкстры найдет маршрут s(s,t)t длины 1 между вершинами s и t, а не минимальный маршрут длины 2+(-2)=0, проходящий через третью вершину графа.

Пример орграфа, для которого неприменим алгоритм Дейкстры.