Алгоритм Флойда

Дан ориентированный граф G=< V, E> с матрицей весов А(Ar­ray [1..N, 1..N] Of Integer).

В результате должна быть сформиро­вана матрица D кратчайших расстояний между всеми парами вершин графа и кратчайшие пути.

Идея алгоритма. Обозначим через Dm[i, j] оценку кратчайшего пути из i в j с промежуточными вершинами из множества [1..т]. Тогда имеем:

D°[i, j]: =A[i, j] и

D(m+1)[i, j]= Min{Dm[i, j], Dm[i, m+1 ] +Dm[m+1, j].

Второе равенство требует пояснения. Пусть мы на­ходим кратчайший путь из i в j с промежуточными вершинами из множества [1..(т+1)]. Если этот путь не содержит вершину (m+1), то D(m+1)[i, j]=Dm[i, j]. Если же он содержит эту вершину, то его можно разделить на две части: от i до (m+1) и от (m+1) до j.

 

Procedure Dist; (*А, D - глобальные структуры данных. *} Var m, i, j: Integer;

Begin

For i: =1 To N Do

For j: =1 To N Do D[i, j]: =A[i, j];

For i: =1 To N Do D[i, i]: =0;

For m: =1 Tо N Do

For i: = 1 To N Do

For j: =1 To N Do D[i, j]: =Min {D[i, j], D[i, m]+D[m, j] };

End;

 

Пример. На рисунке 7 представлены графа и значения мат­риц типа D при работе процеду­ры.

Верхний индекс у D (см. рис.8) указывает номер итерации (значение m в процедуре Dist).

 

 

 

Рис.7

 

Рис. 8

 

Расстояния между парами вершин дает D. Для вывода са­мих кратчайших путей введем матрицу М того же типа, что и D. Элемент M[i, j] определяет предпоследнюю вершину крат­чайшего пути из i в j.

Процедура Dist претерпит небольшие изменения. В том слу­чае, когда D[i, j] больше D[i, m]+D[m, j], изменяется не только D[i, j], но и M[i, j]. M[i, j] присваивается значение М[m, j]. Для нашего примера изменения М отражены на рис.9.

 

Рис.9

 

Например, необходимо вывести кратчайший путь из 3-й вер­шины во 2-ю. Элемент М[3, 2] равен 1, поэтому смотрим на элемент М[3, 1]. Он равен четырем. Сравниваем М[3, 4] с 3-й. Есть совпадение, мы получили кратчайший путь: 3" 4" 1" 2.

Procedure All_Way (i, j: Integer); {*Вывод пути между вершинами i и j. *}

Begin

If M(i, j]=i Then

If i=j Write(i) Else Write (i, '-', j)

Else

Begin All_Way (i, M[i, j]); All_Way (M[i, j ], j);

End;

End;