Модификация Форда
Алгоритм Дейкстры можно модифицировать для случая, когда некоторые из дуг имеют отрицательные длины. Модификация состоит в следующем:
На шаге 2 алгоритма Дейкстры пересчёт величин с помощью соотношения (1) производится для всех вершин, а не только для неокрашенных. Следовательно, числа могут уменьшаться как для неокрашенных, так и для окрашенных вершин.
Если для некоторой окрашенной вершины x происходит увеличение длины , то с этой вершины и инцидентной ей окрашенной дуги окраска снимается.
Процедура алгоритма заканчивается только тогда, когда все вершины окрашены и когда после выполнения шага 2 ни одно из чисел не меняется.
Пример: применим алгоритм Форда к данному графу:
Рис. 45
Окрашиваем вершину s.
Полагаем, что
y = s
Поскольку
,
то вершина t окрашивается,
окрашивается и дуга (s,
t):
Рис. 46
Поскольку не все вершины окрашены, то переходим к шагу 2.
y = t
. . . . . . . . . . . . . . . . . . . .
Т.к. из вершины t не исходит ни одной дуги, все числа d(s), d(a), d(t) остаются неизменными.
Окрашивается вершина а и вместе с ней – дуга (s, a):
Рис. 47
Теперь дерево кратчайших путей имеет вид:
Рис. 48
Все ли вершины окрашены? – Да
Переходим к шагу 2, чтобы попытаться уменьшить числа d(x)
y = a
Поскольку величина d(t) уменьшается от 1 до 0, с вершины t и дуги (s, t) окраска
снимается, и теперь дерево кратчайших путей будет иметь вид:
Рис. 49
В исходном графе остаётся неокрашенной только одна вершина – t. Эта вершина окрашивается вместе с дугой (a, t), поскольку в качестве y на данном шаге фигурирует вершина а.
Дерево кратчайших путей включает дуги: (s, a), (s, t)
Рис. 50
Идём к шагу 3
Все ли вершины окрашены? – Да, все.
Необходимо перейти к шагу 2, чтобы уменьшить величины d(x). Поскольку из вершины t не исходит ни одной дуги, то расстояния d(a), d(t), d(s) не меняются.
Неокрашенных вершин нет.
Переходим к шагу 3.
В графе неокрашенных вершин нет. На шаге 2 расстояние d(x) не изменилось.
Следовательно, алгоритм заканчивает свою работу.
Кратчайший путь - (s, a), (s, t).
Длина пути равна 0.
Замечание:
Алгоритм Форда не решает задачи нахождения кратчайшего пути при наличии в исходном графе контура, имеющего отрицательную длину. Действительно, в этом случае, повторяя неограниченное число раз этот алгоритм для контура, можно получить путь со сколь-угодно малой длиной.
В случае отсутствия сведений о наличии в графе контуров можно применить алгоритм Форда, но в процессе его работы необходимо учитывать сколько раз окрашиваются отдельные вершины. Как только число окрашиваемой какой-либо вершины достигнет величины n (число вершин графа) процедуру алгоритма можно остановить, т.к. исходный граф содержит контур отрицательной длины.
Алгоритмы поиска всех кратчайших путей
Эта задача могла бы быть решена путём многократного применения алгоритма Дейкстры с последовательным выбором каждой вершины графа в качестве вершины S. Однако, существуют алгоритмы более эффективные, чем процедура многократного повторения алгоритма Дейкстры.