Алгоритм определения кратчайших расстояний между всеми парами

 вершин графа (алгоритм Флойда)

Пусть задан граф G=(X,U) и каждой дуге сопоставлена длина, U-множество дуг  l(x_i,x_j)>0.

Шаг 1.

Если между вершинами дуги нет, то вводят фиктивную дугу с l(x_i,x_j)=M₀-большое число и строим матрицу

C₀=(C_ij) n*n-размерностью

   C_ij=  0, для i=j

         l(x_i,x_j),если имеется дуга  (x_i,x_j)

         M₀,если дуги нет

Идея алгоритма состоит в уточнении на каждом шаге x_i и x_j вдоль пути, проходящего через вершину x_k. Если C_ik+C_kj<C_ij, то в качестве нового расстояния берется S_ij=C_ik+C_kj. Рис.

Алгоритм Флойда состоит из n-шагов, выполненных для каждого k. k=1,2,...n. После k-ой итерации элемент C_k матрицы будет  представлять длины кратчайших путей между каждой парой вершин, проходящих только через вершины множества {x₁,...x_k}.

Шаг 2.

k=1

i,j<>k вычисляем новое C_ij=min{C_ij,C_ik+C_kj}

k=k+1

если k<=n, то переход вверх

Если k>n, то переходим вниз.

После окончания расчета мы получаем матрицу S_n, каждый элемент которой дает кратчайшее расстояние между соответствующей парой вершин.

алг Флойда( цел N, вещ таб C[1:N,1:N])

арг N,C

rez C

начало

цел i,j,k

k=1;

пока k<=N

нц

i=1;

пока i<=N

нц

j=1;

пока j<=N

нц

если C[i,j]>C[i,k]+C[k<j],то C[i,j]=C[i,k]+C[k,j] все

j=j+1;кц

i=i+1;кц

k=k+1;кц

конец