3

大学の課題があり、すでに Dijkstra と Bellman-Ford をうまく実装していますが、これについては困っています。すべて問題ないように見えますが、正しい答えが得られません。

コードは次のとおりです。

void FloydWarshall()
{
    //Also assume that n is the number of vertices and edgeCost(i,i) = 0

    int path[500][500];

    /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
       from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to
       edgeCost(i,j) or infinity if there is no edge between i and j.
    */

    for(int i = 0 ; i <= nvertices ; i++)
        for(int j = 0 ; j <= nvertices ; j++)
            path[i][j] = INFINITY;

    for(int j = 0 ; j < narestas ; j++) //narestas = number of edges
    {
        path[arestas[j]->v1][arestas[j]->v2] = arestas[j]->peso; //peso = weight of the edge (aresta = edge)
        path[arestas[j]->v2][arestas[j]->v1] = arestas[j]->peso;
    }

    for(int i = 0 ; i <= nvertices ; i++) //path(i, i) = 0
        path[i][i] = 0;

    //test print, it's working fine
    //printf("\n\n\nResultado FloydWarshall:\n");
    //for(int i = 1 ; i <= nvertices ; i++)
    //    printf("distancia ao vertice %d:  %d\n", i, path[1][i]);


    // Here's the problem, it messes up, and even a edge who costs 4, and the minimum is 4, it prints 2.

    //for k = 1 to n
    for(int k = 1 ; k <= nvertices ; k++)
       //for i = 1 to n
       for(int i = 1 ; i <= nvertices ; i++)
           //for j := 1 to n
           for(int j = 1 ; j <= nvertices ; j++)
               if(path[i][j] > path[i][k] + path[k][j])
                   path[i][j] = path[i][k] + path[k][j];


    printf("\n\n\nResultado FloydWarshall:\n");
    for(int i = 1 ; i <= nvertices ; i++)
        printf("distancia ao vertice %d:  %d\n", i, path[1][i]);
}

私が作成したこのグラフの例を使用しています:

6 7

1 2 4
1 5 1
2 3 1
2 5 2
5 6 3
6 4 6
3 4 2

これは、6 つの頂点 (1 から 6) と、重み 4 の 7 つのエッジ (1,2) があることを意味します。

誰かがさらに情報を必要とする場合は、このコードを見てエラーを見つけられないことにうんざりしています。

4

3 に答える 3

2

気にしないで、私は何かを食べるために休憩を取って、エラーを見つけました.

無限大は INT_MAX として定義されているため、何かを追加するとすぐに負になります。

私は何か大きなものに定義しただけです（私の問題では、over9000のように、グラフパスはそれ以上かかりません）、それはうまく機能しています。

しかし、陰を提案した理由を教えてください。私はそれを取得しませんでした。

ありがとう

于 2010-06-12T02:33:08.637 に答える
0

また、パス上の繰り返しの開始と終了がいくつかの場所で 1 つずつずれていませんか? おそらく、それらを 0 からnvertices-1;まで実行する必要があります。すなわちfor (int i = 0; i < nvertices; i++)。

于 2010-06-12T02:39:30.243 に答える
0 
 if(path[i][j] > path[i][k] + path[k][j])
  path[i][j] = path[i][k] + path[k][j];

ここでいくつかのチェックを行います。たとえば、path[i][k] と path[k][j] が非無限で、i!=ji!=k と k!=j の場合。

于 2010-06-12T02:22:53.590 に答える