?
Solved

find paths using Dijkstra algorithm

Posted on 2010-01-09
3
Medium Priority
?
615 Views
Last Modified: 2012-05-08
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
Comment
Question by:xiromdim
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
3 Comments
 
LVL 53

Accepted Solution

by:
Infinity08 earned 2000 total points
ID: 26274064
>> 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 Comment

by:xiromdim
ID: 26275550
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
 

Author Closing Comment

by:xiromdim
ID: 31675020
he didn't give some code...
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question