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

Рассмотрим теперь алгоритм Флойда, позволяющий отыскивать кратчайшие пути сразу между всеми парами вершин графа. Этот алгоритм реализуется последовательностью следующих шагов:

1. Пронумеровать вершины данного графа: v₁, …, v_m. Составить матрицу L⁰=[l⁰_ij], (i,j=1, …, m), в которой

2. Выполнить итерации в цикле по индексу k=1, …, m, определяя на каждой итерации матрицу L^k=[l^k_ij], (i,j=1, …, m), в которой

l^k_ij=min{l^k-1_ik+l^k-1_kj, l^k-1_ij}.

1. Закончить выполнение алгоритма.

Для того чтобы восстановить кратчайшие пути, найденные в ходе выполнения алгоритма, введем в рассмотрение матрицу P=[p_ij], (i,j=1, …, m). Здесь элемент матрицы p_ij - номер предпоследней вершины в кратчайшем пути, соединяющем вершины v_i и v_j. Если величины p_ij будут известны, можно восстановить кратчайший путь v_i…v_j  в обратном порядке по номерам вершин p_ij=k₁, p_ik1=k₂, …, p_ikn=i.

Рассмотрим сначала так называемый встроенный способ  восстановления пути. При этом нужно дополнить алгоритм Флойда следующими действиями:

-       на шаге 1 положить:   если l⁰_ij<∞, то p⁰_ij=i,  иначе p⁰_ij=0;

-       на шаге 2 положить:   если l^k_ij=l^k-1_ik +l^k-1_kj, то p^k_ij= p^k-1_kj;

если l^k_ij=l^k-1_ij, то p^k_ij = p^k-1_ij .

Внешний способ восстановления пути позволяет решать задачу после того, как работа алгоритма завершена. Располагая матрицами L⁰  и Lⁿ, определяем p_ik=k₁ так, что lⁿ_ik1+l⁰_k1j=lⁿ_ij, p_ik1=k₂ так, что lⁿ_ik2+l⁰_k2k1=lⁿ_ik1 и так далее.