Вся идея алгоритма Флойда заключается в том, что он одновременно решает задачу кратчайшего пути для всех пар вершин в графе, а не для одной конкретной пары i, j
.
Если рассматривать схему реализации из Википедии
for k = 1 to n
for i = 1 to n
for j = 1 to n
W[i][j] = min(W[i][j], W[i][k] + W[k][j])
то вся идея формирования матрицы W
в алгоритме Флойда заключается в том, что новые значения матрицы W
для шага k
формируются на основе "старых" значений матрицы W
(c шага k - 1
). Как вы сами видите, при формировании элемента W[i][j]
используются "старые" значения из посторонных элементов W[i][k]
и W[k][j]
. Они должны быть к этому моменту уже готовы, т.е. полная матрица W
для значения k - 1
должна быть уже сформирована.
То есть для того, чтобы выполнять перевычисление W
на шаге k
нам надо иметь полностью сформированную W
с шага k - 1
. Вот поэтому цикл по k
и сделан самым внешним.
Если вы просто ни о чем не задумываясь поменяете местами циклы
for i = 1 to n
for j = 1 to n
for k = 1 to n
W[i][j] = min(W[i][j], W[i][k] + W[k][j])
то при выполнении внутреннего цикла по k
будет происходить обращение к W[i][k]
и W[k][j]
, которые не имеют никакого отношения к шагу k - 1
(они будут содержать либо начальные значения, либо финальные значения этого элемента) . Алгоритм не будет работать правильно.
Если вам захочется вдруг внешние циклы сделать по i
и j
, то фактически вы будете применять алгоритм Флойда к каждой паре i, j
в отдельности. Получится что-то вроде
for i = 1 to n
for j = 1 to n
{
/* Применяем алгоритм Флойда для пары `i, j` */
/* Переинициализируем матрицу `W` */
for k = 1 to n
/* Формируем матрицу `W` шага `k` для пары `i` И `j` */
for ii = 1 to n
for jj = 1 to n
W[ii][jj]= ...
}
Теперь вам придется формировать полную матрицу шага k
для пары i
И j
- а это снова циклы по ii
и jj
. Такая реализация будет весьма неразумной.
Так как матрица W
шага k
является актуальной для всех пар i, j
одновременно, разумно обрабатывать шаг k
именно так: для всех пар i, j
одновременно.