Алгоритм Флойд-Варшалла - Застрял - PullRequest
Новая
       6

Алгоритм Флойд-Варшалла - Застрял

6 голосов
/ 22 апреля 2010

Я пытаюсь использовать эту логику, чтобы понять, что происходит с матрицей смежности , но я в растерянности, когда говорится о промежуточном расстоянии для 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];

Ответы [ 2 ]

7 голосов
/ 22 апреля 2010

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

Это почти стандартно (и проще) написать это в 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] )

немного более глубокое объяснение состояний находится в Алгоритмист .

4 голосов
/ 22 апреля 2010

Алгоритм Флойда-Варшалла делает следующее:

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

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

"Мой на данный момент самый короткий путь от i до j имеет длину L0, мой на данный момент самый короткий путь от i до k имеет длину L1, мой на данный момент самый короткий путь от k до j длины L2.

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

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

...