var
Matrix: array[1..100, 1..100] of integer //матрица смежности вершин графа 100х100 элементов
count: integer //счётчик, нужен для завершения бесконечного цикла.
.
.
.
.
{Будем считать что матрица уже заполнена известными расстояниями и переменная count
содержит их количество, остальные расстояния, которые нужно найти имеют значение 0}
begin
iter: //цикл, реализованный с помощью меток, означает итерации, можно заменить циклом While count<100*100-100. Просто так нужно было решать, здесь нет остального кода.
if count>=100*100-100 then //если рассчитаны все элементы матрицы
goto exit; //тогда выход из цикла (exit)
else
begin
for i:=1 to 100 do //собственно перебор элементов матрицы, вместе со следующей строчкой, i-строка j-столбец
for j:=1 to 100 do
if i<>j then //если не попали на диагональ, то...
if Matrix[i,j]>0 then //попали на непустой элемент матрицы
for k:=1 to 100 do //когда попали на непустой элемент, пытаемся найти второй непустой элемент, который в сумме с первым даст нам новый элемент (новое значение расстояния), при этом адрес заполняемого элемента будет i - строка, k - столбец
if i<>k then //если не попали на диагональ, то...
if Matrix[j,k]>0 then //попали на непустой элемент матрицы
if Matrix[i,k]=0 then //если по адресу [i,k], содержится пустой элемент то...
begin
Matrix[i,k]:=Matrix[i,j]+Matrix[j,k]; //записываем новый элемент матрицы
count:=count+1; //увеличиваем количество заполненных элементов матрицы на 1
end
else //иначе, если не [i,k]=0
if Matrix[i,k]>Matrix[i,j]+Matrix[j,k] then //если по адресу [i,k], содержится элемент, значение которогого больше чем сумма элементов по адресам [i,j] и [j,k], то...
Matrix[i,k]:=Matrix[i,j]+Matrix[j,k]; //переписываем элемент матрицы
end;
goto iter; //возврат к iter
exit: //выход из цикла
end.
Выдрал кусок из рабочей программы и добавил комментарии, это лишь общий вид, не факт что будет работать оторванное от остальной программы. Ввиду специфики решённой с помощью этого куска кода задачи, незаполненные элементы матрицы смежности имеют значения 0 а не бесконечность. Это добавляет несколько дополнительных действий, от них можно избавиться.
ТС, последняя таблица, что вы представили - это уже рассчитанная матрица кратчайших расстояний, в матрице смежности вершин заполнены не все элементы, незаполненные имеют расстояние равное либо 0 либо бесконечность, смотря как вы собираетесь решать задачу. Т.е. в матрицу смежности записываются лишь расстояния между СОСЕДНИМИ вершинами графа. Она является базовой для расчёта по алгоритму Флойда. Есть обратный алгоритм для нахождения пути по матрице кратчайших расстояний.
Повторюсь, код оторванный от всего остального может быть немного корявым, но этого должно хватить для понимания концепции решения поставленной задачи. А далее можно уже эксперементировать, отлаживать, оптимизировать...
//когда попали на непустой элемент, пытаемся найти второй непустой элемент, который в сумме с первым даст нам новый элемент (новое значение расстояния), при этом адрес заполняемого элемента будет i - строка, k - столбец
это суть алгоритма, остальное - бутафория и зависит от реализации конкретной задачи конкретным программистом.
отвечаю на вопрос в личке
Вот граф:
⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.
Вот матрица смежности вершин для него
⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.
Вообще-то пишут в инете что что она бинарная, т.е. заполненные элементы=1, остальные=0. Так что возможно я не прав называя эту матрицу матрицей смежности. Но я понимаю так, может где-то в литературе читал - не везде одно и то же пишут. Но именно такая матрица, а не бинарная необходима для расчёта алгоритмом флойда.
всё что делает Флойд - это складывает элементы матрицы по определённому алгоритму. В итоге, каждый новый элемент является суммой неких двух уже заполненных ранее. Это то же самое, что найти сначала суммы всех звеньев имеющих общую вершину, затем из полученного складывать дальше, получая уже не 2-х звенные, а 3-х, 4-х звенные, потом 5-8 звенные и т.д., оставляя при этом лишь кратчайшие, а не все варианты.
но проблема в том что я не вижу как это все связать. чтобы был такой же детальный просчет как и на вышеуказанном сайте
((((((
На Флойда вроде не похоже... Может пригодится. И подобных программок на просторах инета полно, с исходниками - надо искать.
