Логика алгоритма Floyd-Warshall - застрявший

Question

Логика алгоритма Floyd-Warshall - застрявший

Я пытаюсь использовать эту логику для понимания то, что продолжает матрицу смежности, но я в широком масштабе смущен, где она говорит о расположении с интервалами для b c d.....

Кто-либо мог объяснить, что продолжается здесь?

Спасибо (отмеченный, поскольку Java, поскольку это - язык, это было продемонстрировано нам в, поэтому если кто-либо отправил какие-либо примеры кода, они видели его, был на том языке),

http://compprog.wordpress.com/2007/11/15/all-sources-shortest-path-the-floyd-warshall-algorithm/

Вот код:

for (k = 0; k < n; ++k) {
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            /* If i and j are different nodes and if
               the paths between i and k and between
               k and j exist, do */
            if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                /* See if you can't get a shorter path
                   between i and j by interspacing
                   k somewhere along the current
                   path */
                if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
                        (dist[i][j] == 0))
                    dist[i][j] = dist[i][k] + dist[k][j];

6

java algorithm revision floyd-warshall

задан keelar 2 July 2013 в 05:26

2 ответа

Другие вопросы по тегам:

java algorithm revision floyd-warshall

Похожие вопросы:

score 4 · Answer 1

Алгоритм Флойда-Уоршалла выполняет следующие действия:

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

Это выглядит так:

«Мой текущий кратчайший путь от i до j имеет длину L0 , мой текущий кратчайший путь от i до k имеет длину L1 , мой в настоящее время кратчайший путь от k до j имеет длину L2 .

Что, если я объединю кратчайшие на данный момент пути i к k и k к j в новый путь? Будет ли этот новый путь i к k к j короче моего текущего кратчайшего пути от i до j ? Если это так, он суммирует длины L1 и L2 для вычисления длины нового кратчайшего пути. путь. "

Это означает, что k является потенциальной точкой остановки на пути от i до j .

score 7 · Answer 2

Флойд-Уоршалл - проблема динамического программирования .

Это почти стандартно (и проще) писать в 2-размерная версия:

for ( int k = 0; k < n; k++ )
   for ( int i = 0; i < n; i++ )
      for ( int j = 0; j < n; j++ )
          dist[i][j] = min( dist[i][k] + dist[k][j], dist[i][j] )

, но, возможно, это поможет вам представить это в трехмерной версии, чтобы вы могли видеть все состояния более подробно:

for ( int k = 0; k < n; k++ )
   for ( int i = 0; i < n; i++ )
      for ( int j = 0; j < n; j++ )
          dist[k][i][j] = min( dist[k-1][i][k] + dist[k-1][k][j], dist[k-1][i][j] )

немного более глубокое объяснение состояний можно найти в Algorithmist ].