Thread: Glitch with Dijkstra's Algorithm

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    25

    Question Glitch with Dijkstra's Algorithm

    Hello,


    I'm working on implementing Dijkstra's Algorithm in C, and have run into a glitch. I can't seem to tack down the source of the glitch, but whenever I give my program the 25 node matrix, the first 20 nodes all calculate properly, but the last 5 are defaulting to as if there was a direct path from source to them, when there isn't.

    Here's the code:

    Code:
    #include <stdio.h>#include <time.h>
    #define infinity 998
    #define MAX 25
    
    
    int prev[25];
    
    
    void printPath(int index)
    {
        if (prev[index] > 0)
        {
            printPath(prev[index]);
        }
        if(prev[index] == 0 || prev[index] == -1)
            printf("1 ");
        printf("%d ", index+1);
    }
    
    
    void lowestCost(int nodes, int startN, int cost[MAX][MAX], int *distance) //Dijkstra's Algorithm Function
    {
        int i,j,count,k,flag[MAX],min;
        
        for(i=0;i<nodes;i++)
        {
            flag[i] = 0;
            distance[i] = cost[startN][i]; //fill in initial known distances from start node to neighbors.
            if(distance[i] != infinity)
            {
                prev[i] = startN;        //set parent as the start node if distance is not infinity.    
            }
            else 
            {
                prev[i] = -1;        //no path found yet, need to dig deeper.    
            }
        }
        count = 0;
        while(count<=nodes)
        {
            min=100;
            
            for(j=0;j<nodes;j++)
            {
                if(distance[j]<min && !flag[j])
                    min=distance[j],k=j;
            }
            
            flag[k]=1;
            count++;
            
            for(j=0;j<nodes;j++)
            {
                if(((distance[k]+cost[k][j]<distance[j]) || distance[j] == infinity) && !flag[j]) //new route found, shorter distance calculated.
                    {
                    distance[j]=distance[k]+cost[k][j];
                    prev[j] = k;    //update path
                    }
            }
        }
    }
    
    
    int main( )
    {
        int nodes, startN, i, j, cost[MAX][MAX], distance[MAX];
        int t;
        t = clock();
        
        nodes = 25;
    
    
        for(i=0; i< nodes; i++)
        {
            for(j=0; j<nodes; j++)
            {
                scanf("%d",&cost[i][j]);
                if(cost[i][j] == 0) 
                    cost[i][j] = infinity;
            }
        }
        
        for(i = 0; i < nodes; i++)
            prev[i] = -1;
        
        startN = 0;
        
        lowestCost(nodes, startN, cost, distance);
    
    
        int z;
        
        for(z = 1; z < nodes; z++)
        {
            printf(" %dc %fs Path to %d: ", t, ((float)t/10000), z+1);
            printPath(z);
            printf("\n");
        }
        
        return 0;
    }

    Here's the matrix:

    Glitch with Dijkstra's Algorithm-matrix-jpg

    The output I've been getting so far is the following:

    1502c 0.150200s Path to 2: 1 2 1502c 0.150200s Path to 3: 1 12 3
    1502c 0.150200s Path to 4: 1 2 4
    1502c 0.150200s Path to 5: 1 2 4 5
    1502c 0.150200s Path to 6: 1 2 4 5 6
    1502c 0.150200s Path to 7: 1 2 4 5 6 7
    1502c 0.150200s Path to 8: 1 2 4 5 8
    1502c 0.150200s Path to 9: 1 2 4 5 8 9
    1502c 0.150200s Path to 10: 1 2 4 5 10
    1502c 0.150200s Path to 11: 1 2 4 5 10 11
    1502c 0.150200s Path to 12: 1 12
    1502c 0.150200s Path to 13: 1 2 4 5 10 13
    1502c 0.150200s Path to 14: 1 2 4 5 10 14
    1502c 0.150200s Path to 15: 1 2 4 5 10 13 15
    1502c 0.150200s Path to 16: 1 12 16
    1502c 0.150200s Path to 17: 1 12 17
    1502c 0.150200s Path to 18: 1 2 4 5 10 13 18
    1502c 0.150200s Path to 19: 1 12 19
    1502c 0.150200s Path to 20: 1 12 20
    1502c 0.150200s Path to 21: 1 2 4 5 10 13 15 21
    1502c 0.150200s Path to 22: 1 12 22
    1502c 0.150200s Path to 23: 1 12 23
    1502c 0.150200s Path to 24: 1 12 24
    1502c 0.150200s Path to 25: 1 12 25
    Ignore the time calculations, those are still being worked on after getting the algorithm working 100%.

    Thank you for your time, and feedback.


    --

    Alex

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    It would be a hell of a lot easier if your matrix was an attached text file rather than a picture.

    Then it would be relatively easy for us to actually run your code and observe what is happening.

    Why is prev a global variable?
    Declare it in main, and pass it as a parameter to the functions.

    Which OS/Compiler are you running this on?
    If it's some ancient fossil like TurboC, then you could have already blown the stack allocation with your large 2D array.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Sep 2011
    Posts
    25
    I was having issues with the matrix formatting when copying it to the forum. Here's a google drive link to the dat file with the matrix. I use cygwin gcc to compile the code. It runs with unix redirection "./a.out < input.dat"

    Here's the file:
    https://docs.google.com/file/d/0BxLYBzcf5U5aWmxBeXVDOVQyUmM/edit?usp=docslist_api
    Last edited by alexhollis; 05-01-2015 at 10:21 AM. Reason: forgot link

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    You can post .txt files as an attachment.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Sep 2011
    Posts
    25

    Post Matrix File:

    Here's the matrix for input.

    To use, redirect stdio Unix style "./a.out < input.txt"

    --

    Thanks


    Alex
    Attached Files Attached Files

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    I changed min=100 to min=1000 and got different results.

    You might want to go through your code and replace the remaining magic numbers with suitable #define'd constants.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dijkstra's Algorithm?
    By mmhawk607 in forum C++ Programming
    Replies: 1
    Last Post: 04-15-2013, 12:13 PM
  2. Dijkstra Algorithm - Not Getting it..
    By johnnyzithers in forum C Programming
    Replies: 1
    Last Post: 10-06-2009, 11:18 PM
  3. Help w/Dijkstra's algorithm
    By dudeomanodude in forum C++ Programming
    Replies: 1
    Last Post: 04-22-2008, 02:26 PM
  4. Dijkstra algorithm problem.
    By apacz in forum C++ Programming
    Replies: 5
    Last Post: 05-28-2005, 04:16 PM
  5. Dijkstra algorithm
    By Micko in forum C++ Programming
    Replies: 5
    Last Post: 04-30-2004, 05:21 AM

Tags for this Thread