Аналогично корректируются метки всех оставшихся вершин, а именно,
D[v3] = min (D[v3], D[v2]+c23, D[v4]+c43, D[v5]+c53, D[v6]+c63) = (5,7+¥, 5+¥, 2+1, 12+¥) = 3,
D[v4] = min (D[v4], D[v2]+c24, D[v3]+c34, D[v5]+c54, D[v6]+c64) = (5,7+¥, 3+¥, 2+2, 12+¥) = 4,
D[v5] = min (D[v5], D[v2]+ c25, D[v3]+ c35, D[v4]+ c45, D[v6]+ c65) = (2,7+¥, 3+¥, 4+¥, 12+¥) = 2,
D[v6] = min (D[v6], D[v2]+ c26, D[v3]+ c36, D[v4]+ c46, D[v5]+ c56) = (12,7+2, 3+¥, 4+¥, 2+¥) = 9.
Т.к. метки вершин изменились, то продолжаем процесс дальше. Результаты третьей и четвертой итераций совпали, значит итерационный процесс можно закончить, кроме того k = n-2 = 4.
Величины, стоящие в последнем столбце, и дают длины минимальных путей из вершины v1 до всех остальных вершин. Например, длина минимального пути из v1 в v2 равна 5, сам путь имеет вид: v1v5v3v2.
Очевидно, что задачу определения расстояния между всеми парами вершин можно решить, используя n раз (поочередно для каждой вершины) один из описанных ранее алгоритмов. Однако оказывается, что n-кратное использование этих алгоритмов не является наилучшим методом. Рассмотрим более эффективный алгоритм для решения поставленной задачи – алгоритм Флойда.
Идея этого алгоритма следующая. Рассмотрим орграф D = (V,X), где V={v1,…,vn}. Обозначим через dij(m) длину кратчайшего из путей из vi в vj с промежуточными вершинами из множества {v1,…,vm}.
Тогда имеем следующие уравнения:
dij(0) = cij,
dij(m+1) = min ( dij(m), dim(m) + dmj(m)).
Обоснование второго уравнения достаточно простое. Рассмотрим кратчайший путь из vi в vj с промежуточными вершинами из множества {v1,…, vm,vm+1}. Если этот путь не содержит vm+1 , то dij(m+1) = dij(m) . Если же он содержит vm+1 , то, деля путь на отрезки от vi до vm+1 и от vm+1 до vj , получаем равенство dij(m+1) = dim(m) + dmj(m) . Приведенные уравнения дают возможность вычислить расстояния d(vi,vj) = dij(n) , где 1 £ i, j £ n.
А л г о р и т м Ф л о й д а
Данные: матрица весов С(D) орграфа D.
Результат: расстояния между всеми парами вершин D[i,j] = d(vi,vj).
1. Для всех i = 1,…,n , j = 1,…,n положим D[i,j] = cij .
2. Для всех i = 1,…,n положим D[i,i] = 0.
3. Положим m = 1.
4. Положим i = 1.
5. Положим j = 1.
6. D[i,j] = min ( D[i,j], D[i,m] + D[m,j] ).
7. Если j < n, то положим j = j + 1 и переходим к шагу 6.
8. Если i < n, то положим i = i + 1 и переходим к шагу 5.
9. Если m < n, то положим m = m + 1 и перейдем к шагу 4, иначе алгоритм заканчивает работу. Полученные значения D[i,j] дают расстояния между вершинами vi и vj .
Замечание. Дополнить описанный алгоритм шагами, позволяющими находить сам путь от вершины vi до вершины vj.
Пример. Определим длины минимальных путей между любыми парами вершин орграфа, изображенного на рис.1. Все вычисления будем проводить с помощью матриц D.
m = 1 m = 2
| v1 | v2 | v3 | v4 | v5 | v6 | v1 | v2 | v3 | v4 | v5 | v6 | ||
| v1 | 0 | ¥ | 5 | 5 | 2 | 12 | v1 | 0 | ¥ | 5 | 5 | 2 | 12 |
| v2 | ¥ | 0 | ¥ | ¥ | ¥ | 2 | v2 | ¥ | 0 | ¥ | ¥ | ¥ | 2 |
| v3 | ¥ | 2 | 0 | ¥ | ¥ | ¥ | v3 | ¥ | 2 | 0 | ¥ | ¥ | ¥ |
| v4 | ¥ | 2 | ¥ | 0 | ¥ | ¥ | v4 | ¥ | 2 | ¥ | 0 | ¥ | ¥ |
| v5 | ¥ | ¥ | 1 | 2 | 0 | ¥ | v5 | ¥ | ¥ | 1 | 2 | 0 | ¥ |
| v6 | ¥ | ¥ | ¥ | ¥ | ¥ | 0 | v6 | ¥ | ¥ | ¥ | ¥ | ¥ | 0 |
Положим m = 1. Если i = 1 или j = 1, то элементы матрицы остаются без изменения, т.к. D[i,j] = min ( D[i,j], D[i,m] + D[m,j] ). Поэтому рассмотрим случай, когда i = 2 , а j = 3. Тогда D[2,3] = min ( D[2,3], D[2,1] + D[1,3] ) = min (¥,¥+5) = ¥. Далее, j = 4, т.е. D[2,4] = min(D[2,4], D[2,1] + D[1,4] ) = min (¥,¥+5) = ¥. Продолжаем процесс до тех пор, пока i £ 6 и j £ 6. Положим m = 2 и продолжим рассуждения дальше.