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

Потому что идея состоит в том, чтобы попытаться улучшить пути, пытаясь пройти через узел k на каждом шаге, чтобы улучшить каждый i - j путь.

Обозначения не имеют значения, вы можете использовать i, j, k в качестве переменных цикла вместо k, i, j, если хотите, но вы должны помнить о приведенной выше логике. В этом случае вы захотите попытаться улучшить j - k пути, пройдя i на каждом шаге:

for i = 0, n
  for j = 0, n
    for k = 0, n
      if d[j, i] + d[i, k] < d[j, k]
        d[j, k] = d[j, i] + d[i, k]

Вы не можете просто переупорядочить циклы for без изменения условия, потому что таким образом вы получаете другой алгоритм - кто знает, что он делает.

In

for (k = 0; k < n; ++k)
  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
      if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

Самый внешний цикл k относится к вершинам, которые могут находиться на пути между Vi и Vj. Итак, когда, например, k=1, вы рассматриваете все пути между вершинами Vi и Vj, которые включают вершину V1, как в

Vi .... V1 .... Vj

Что еще более важно, из этих путей вы выбираете лучший с релаксацией.

if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

Опять же, каждая итерация фокусируется на двух вершинах Vi и Vj и выбирает лучший путь между ними.

В другом вашем случае, неудачном, вы не выбираете лучший среди путей между двумя фиксированными вершинами Vi и Vj, вместо этого вы расслабляетесь повсюду, никогда не дожидаясь достаточно времени, чтобы выяснить, какой путь между двумя установленными вершинами является правильным. Лучший.

На Geekviewpoint, сайте, на который я очень полагаюсь, они явно используют x и v как вершины и t для самого внешнего цикла, что позволяет легко запомнить, что t является временным и поэтому не является одной из конечных точек. (Хотелось бы, чтобы они на самом деле объяснили это, потому что это не очевидно для всех.)

//dynamically find the shortest distance between each pair.
    for (int t = 0; t < n; t++) {
      for (int v = 0; v < n; v++) {
        for (int u = 0; u < n; u++) {
          if (dist[v][u] > (long) dist[v][t] + dist[t][u]) {
            dist[v][u] = dist[v][t] + dist[t][u];
            pred[v][u] = pred[t][u];
          }
        }
      }
    }

Я нашел контрпример для второго ошибочного алгоритма.
Когда i = 0, j = 1, он попытается найти посредника, но его нет.
Затем, когда посредник будет доступен для i = 0 , j = 1 больше не проверяется.

В основном, когда у вас есть значение K в loop k, это означает, что вы собираетесь добавить еще одно ребро, и все возможные пути перехода от (i->j) обновляются с помощью edge(1->K-1). Затем вы вставляете еще одну кромку K и снова проверяете, есть ли способ перейти от (i->j) более дешевым способом, используя эту кромку. так ты пишешь d[i][j]=min(d[i][j],d[i][k]+d[k][j]).

Итак, если вы хотите написать

  for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
     for(int k=0;k<n;k++)

Ваше обновление должно быть d[j][k] = min(d[j][k],d[j][i]+d[i][k])