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

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;
}

Open in new window

0
xiromdim
Asked:
xiromdim
  • 2
1 Solution
 
Infinity08Commented:
>> 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
 
xiromdimAuthor 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++;
     }
  }

Open in new window

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

Featured Post

Receive 1:1 tech help

Solve your biggest tech problems alongside global tech experts with 1:1 help.

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