*поиска кратчайших расстояний расстояний между всеми парами вершин графа (одновременно можно построить и сами кратчайшие пути от каждой вершины до каждой)
*построения матрицы достижимости графа
*построения множества истоков и множества стоков (исток - вершина, в которую нет входящих дуг) (сток - вершина, из которой нет исходящих дуг)
Алгоритм Флойда
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Входные данные
В первой строке входного файла 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 //Считываем граф 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 begin for j:=1 to n do write(g[i,j],' '); writeln; end; end.