0

I'm trying to implement the Dijkstra algorithm in C, I understand the algorithm and know how it works, but I just don't know how I can catch the path it does. Do anyone have a clue?

#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

The output I want out from the program is 0 - > 3: 13 or something like that...

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到 的最短路径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 回答