0

私は C で Dijkstra アルゴリズムを実装しようとしています。アルゴリズムを理解し、その仕組みを知っていますが、そのパスをキャッチする方法がわかりません。誰か手がかりを持っていますか？

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define INF 1000
#define NUM_OF_NODES 4
#define MEMBER 1
#define NOMEMBER 0

void dijkstra(int weight[][NUM_OF_NODES],int s,int t,int *pd, int precede[])
{
    int distance[NUM_OF_NODES],perm[NUM_OF_NODES],prev[NUM_OF_NODES];
    int current,i,j,k,dc;
    int smalldist,newdist;
    for (int i = 0; i < NUM_OF_NODES; i++)
    {
        perm[i] = NOMEMBER;
        distance[i] = INF;
        prev[i] = -1;
    }

perm[s] = MEMBER;
distance[s] = 0;
current = s;

while(current != t)
{
    smalldist = INF;
    dc = distance[current];
    for (int i = 0; i < NUM_OF_NODES; i++)
    {
        if (perm[i] == NOMEMBER)
        {
            newdist = dc + weight[current][i];
            if (newdist < distance[i])
            {
                distance[i] = newdist; // Count the updated distance
                precede[i] = current;

            }
        if (distance[i] < smalldist)
        {
            smalldist = distance[i];
            k = i;
        }

        }
    }//end of for and if

    current = k;
    perm[current] = MEMBER;

}//end while
*pd = distance[t];
} //end of function

プログラムから出力したい出力は 0 - > 3: 13 またはそのようなものです...

4

1 に答える 1

2

私が知る限り、先行するノードの配列がすぐそこにあります。

その場合、パスの出力はそれを通過するのと同じくらい簡単でなければなりません

void print_path(int s, int t, int precede[]) {
    int current = t;

    while (current != s) {
        printf("%d -> ", current);
        current = precede[current];
    }

    printf("%d\n",current);
}

tからまでの最短経路を 1 つ出力しsます。

編集

次のように実行します。

int precede[NUM_OF_NODES];
dijkstra(weight,s,t,pd, precede);
print_path(s,t,precede); // will print shortest a path from t to s
于 2013-09-04T16:36:02.380 に答える