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

Рассмотрим взвешенный орграф G с N вершинами. Алгоритм Флойда находит в нем длину минимальных путей из каждой вершины в каждую.

Реализация алгоритма предельно проста. Мы будем записывать решение в массив V размера NxN: V[i,j] - длина минимального пути из i в j. Вначале V=G. Мы пробегаем все вершины j,i,k и, в том случае если V[i,k] больше чем V[i,j]+V[j,k], то есть пройти из i в k через j быстрее, чем напрямую, мы изменяем значение V[i,k] на V[i,j]+V[j,k].

Алгоритм Флойда работает для любых, в том числе и отрицательных, весов ребер графа. Если в графе есть цикл отрицательного веса, то после окончания работы алгоритма для некоторой вершины i будет V[i,i]<0.

Очевидно, что алгоритм Флойда требует O(N^3) операций и O(N^2) дополнительной памяти (для хранения массива V).

Реализация алгоритма:

const
  MaxN = 100;

var
  N : Integer;
  G : array [1 .. MaxN,1 .. MaxN] of Integer;
  V : array [1 .. MaxN,1 .. MaxN] of Longint;

procedure Floyd;
var
  I,J,K : Integer;
begin
  for I:=1 to N do
  for J:=1 to N do
    V[I,J] := G[I,J];
  for I:=1 to N do
    V[I,I] := 0;
  for J:=1 to N do
  for I:=1 to N do
  for K:=1 to N do
    if (V[I,J]<>-1) and (V[J,K]<>-1) and
    ((V[I,K]=-1) or (V[I,K]>V[I,J]+V[J,K])) then
      V[I,K] := V[I,J] + V[J,K];
end;

Отредактировано Berd (2007-06-20 10:11:47)