• Status: Solved
• Priority: Medium
• Security: Public
• Views: 618

# find paths using Dijkstra algorithm

I have the code below implementing Dijkstra algorithm to find shortest paths from a node to all others. I want to keep truck of the path to visit each node. How can I do it? With another 2D array?
Thanks
``````#include <stdio.h>
#define MAX 7
#define INFINITE 998

int allselected(int selected[])
{
int i;
for(i=0;i<MAX;i++)
if(selected[i]==0)
return 0;
return 1;
}

void shortpath(int cost[][MAX],int preced[],int distance[])
{

int selected[MAX]={0};
int current=0,i,k,dc,smalldist,newdist;

for(i=0;i<MAX;i++)
distance[i]=INFINITE;

selected[current]=1;

distance[0]=0;
current=0;

while(!allselected(selected)){
smalldist=INFINITE;
dc=distance[current];
printf("current node: %d\n",current);
for(i=0;i<MAX;i++){
if(selected[i]==0){
newdist=dc+cost[current][i];
if(newdist<distance[i]){
distance[i]=newdist;
preced[i]=current;
}
if(distance[i]<smalldist){
smalldist=distance[i];
k=i;
}
}
}
for(i=0;i<MAX;i++) printf("%d ",preced[i]);getchar();
current=k;
selected[current]=1;
}
}

int main()
{
int cost[MAX][MAX]={
{0,1,1,0,0,0,0},
{1,0,0,1,1,0,0},
{1,0,0,0,0,1,0},
{0,1,0,0,0,0,0},
{0,1,0,0,0,0,0},
{0,0,1,0,0,0,1},
{0,0,0,0,0,1,0}
};
int i,preced[MAX]={0},distance[MAX], j;

for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
if(cost[i][j]==0) cost[i][j]=INFINITE;
shortpath(cost,preced,distance);

for(i=0;i<MAX;i++){
printf ("from :%d -> %d  : ",0, i);
printf("%d\n",distance[i]);
}

printf("\n    PRESS ANY KEY TO CONTINUE \n");
getchar();
return 0;
}
``````
0
xiromdim
• 2
1 Solution

Commented:
>> I want to keep truck of the path to visit each node.

The result of Dijkstra's algorithm should implicitly give you all shortest paths, assuming it's implemented correctly.

In your implementation, the preced array contains the information you need. From any target node, you can back-track to the source node, using this array.
0

Author Commented:
ok! this is the code
``````void find_paths(int paths[][N], int previous[]){
int path_index, source, sink, cur, prev;

//initialize paths array
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
paths[i][j]=-1;

sink=0;
for(source=0; source<N; source++){
path_index=0;
cur = prev = source;

while(prev != sink){
prev = previous[cur];
cur = prev;
paths[source][path_index] = cur;
path_index++;
}
}
``````
0

Author Commented:
he didn't give some code...
0

## Featured Post

• 2
Tackle projects and never again get stuck behind a technical roadblock.