Thread: Dijkstra Algorithm - Not Getting it..

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    2

    Dijkstra Algorithm - Not Getting it..

    Hello, this is my first C program and the first time I have posted here.. or anywhere for code help.
    My issue is in my understanding of the dijkstra algorithm. I get the talked-out version.. and have read many different explanations. I thought I had it straight.. but after coding it, it's wrong.

    Code:
    void dijkstra(char start[MAXLENGTH]){
    	int startInt;
    	int endInt;
    	int s[MAXLENGTH];
    	int min = -1;
    	int z = 0;
    	
    	for(z = 0; z <= count; ++z){
    		d[z] = MAXINT;
    		s[z] = 0;
    	}
    	
    	endInt = cityToInt(end);
    	startInt = cityToInt(start);
    	d[startInt] = 0;
    	
    	for(w = 0; w < count; w++){
    		s[startInt] = 1;
    		min = -1;
    		for(z = 0; z < count; z++){
    			if(s[z]==0 && (min == -1 || d[z] < d[min])){
    				min = z;
    			}
    		}
    		
    		s[min] = 1;
    	
    		for(v = 0; ((s[v]==0) && (graph[u][v] != 0));v++){
    			
    			
    			if(d[min] + graph[min][v] < d[v]){
    				
    				d[v] = d[min] + graph[min][v];
    				p[v] = min;
    				printf("P[%d] = %d\n",z,p[z]);
    
    			}
    		}		
    	}
    }
    The program uses this function after compiling graph[t][f], where the entry in [t][f] is the distance from those cities.
    After running dijkstra.. if I print d[endCity] I get 5000 (defined as my MAXINT) instead of the distance from the startCity to the endCity.
    If I print p[endCity] down to p[0], they all have the same value: 0

    Any help is greatly appreciated.

  2. #2
    Registered User
    Join Date
    Oct 2009
    Posts
    2
    I should give you the definitions at the start of the program..

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXLENGTH 80
    #define MAXCITY 100
    #define MAXINT 5000
    
    char city[MAXCITY][MAXLENGTH];
    char graph[MAXCITY][MAXLENGTH]; 
    char start[MAXLENGTH];	
    char end[MAXLENGTH];
    int dist[MAXLENGTH];
    int d[MAXLENGTH];
    int p[MAXLENGTH];
    int count = 0;
    int v = 0;
    int u = 0;
    int w = 0;
    int s[MAXLENGTH];

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dijkstra algorithm problem.
    By apacz in forum C++ Programming
    Replies: 5
    Last Post: 05-28-2005, 04:16 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Dijkstra algorithm
    By Micko in forum C++ Programming
    Replies: 5
    Last Post: 04-30-2004, 05:21 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM