..:GraphTheory:.. [ Алгоритмы. Алгоритм Флойда ]

$Эмблема$

Теория графов. Определения. Алгоритмы. Исходники

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

Кратчайшие пути между всеми парами вершин. Алгоритм Флойда

Пусть требуется найти кратчайшие пути между всеми парами вершин графа. Алгоритм Флойда позволяет сделать это за время O(n³).
Итак, есть граф G=(V,E), каждой дуге [i,j] которого сопоставлена стоимость C[i,j]. В результате должна быть получена матрица кратчайших путей A размера nxn, где n - количество вершин в графе.
Вычисления проводятся за n итераций.
Для любого k=0..n обозначим через Ak[i,j] значение длины кратчайшего пути из вершины i в вершину j при использовании вершин с номерами не более k.
Отсюда,

A⁰[i,j]=C[i,j]
A^k+1[i,j]=min(A^k[i,j],A^k[i,k+1]+A^k[k+1,j])

В нижней формуле выбор осуществляется меньшего из двух путей: содержащего вершину (k+1) и не содержащего ее.

Скачать исходник (Pascal)