Алгоритм Флойда, применяется для
*поиска кратчайших расстояний расстояний между всеми парами вершин графа (одновременно можно построить и сами кратчайшие пути от каждой вершины до каждой)
*построения матрицы достижимости графа
*построения множества истоков и множества стоков (исток - вершина, в которую нет входящих дуг) (сток - вершина, из которой нет исходящих дуг)

Рассмотрим алгоритм Флойда на одноименной задача на acmp.ru задача номер 135

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

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

В первой строке входного файла INPUT.TXT записано единственное число N (1 <= N <= 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы - всегда нули.

Выходные данные

В выходной файл OUTPUT.TXT выведите N строк по N чисел - матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.

Пример

INPUT.TXT

4
0 5 9 100
100 0 2 8
100 100 0 7
4 100 100 0

OUTPUT.TXT

0 5 7 13
12 0 2 8
11 16 0 7
4 9 11 0

Код:
var g:array [1..100,1..100] of longint; n,j,i,k:longint;
function min(x,y:longint):longint;
begin
 if x<y then min:=x
         else min:=y;
end;         
begin
assign(input,'input.txt'); reset(input);
  assign(output,'output.txt'); rewrite(output);
 {Считываем граф}
 readln(n);
 for i:=1 to n do
  for j:=1 to n do read(g[i,j]);
 {Вот это - алгоритм Флойда, т.е простейший для реализации способ нахождения кратчайших расстояний от каждой вершины к каждой} 
 for k:=1 to n do
     for i:=1 to n do
        for j:=1 to n do
           G[i,j]:=min(G[i,j],G[i,k]+G[k,j]);
 {Вывод полученного графа}
 for i:=1 to n do
  for j:=1 to n do begin 
   {Хитрый вывод по 4 числа в строке}
   write(g[i,j],' ');
   if ((j mod 4=0)) then  
   writeln;
   end;  
end.   
 {Если сдавать на acmp будете, не катайте тупо =) }