Романовский И.В.

Алгоритм Уоршелла-Флойда

Источник:
  Романовский И.В. Дискретный анализ: Учебное пособие для студентов, специализирующихся на прикладной математике и информатике. — 3-е изд., перераб. и доп. — СПб.: Невский Диалект; БХВ-Петербург, 2003. - с.215-216

При построении матрицы кратчайших расстояний между всеми вершинами графа используется идея построения на первоначальном этапе матрицы v(М,М) возможных одношаговых переходов из каждой вершины в каждую (т.е. в результате выполнения алгоритма образуется матрица кратчайших расстояний от любой одной вершины графа до любой другой или до самой себя):

v[i,k]=min{l[u]|beg u=i, end u=k}

где v[i,k] – кратчайшее расстояние между вершинами i и k
beg u – начало дуги
end u – конец дуги
min{l[u]|beg u=i, end u=k} – минимальное значение длины дуги и, начало которй в вершине i, а конец дуги соответствует вершине k.

A затем эта матрица пересчитывается тройным циклом по множеству вершин, причем внешний цикл - по промежуточной вершине:

for (i in M) do
    for (i1,i2 in M) do
      if ( v[i1,i2] > v[i1,i]+v[i,i2] ) then
        v[i1,i2]:= v[i1,i]+v[i,i2]
      end
    end
end

Cмысл алгоритма в том, что когда при фиксированном i перебираются все возможные пары i1 и i2, то происходит сравнение лучшего из имеющихся к данному моменту путей от i1 до i2 путем, составленным из лучшего пути от i1 до i и лучшего пути от i до i2., и в результате этого сравнения может быть улучшен путь от i1 до i2.

Сам путь, на котором достигается максимум, легко строится, если одновременно с матрицей v пересчитывать матрицу d[M,M], в которой d[i,k] – выходящая из i дуга, с которой начинается путь, ведущий в k (для пересчета этой матрицы при каждом исполнении оператора присваивания внутри тройного цикла должен исполняться еще один оператор d[i1,i2]:=d[i1,i] - переход изi1 в i2 должен быть таким же, как в i). По завершении расчетов путь из любой вершины в любую легко создается по данным матрицы d. <…>