3
\$\begingroup\$

I wrote a program which finds the shortest path between a source and a destination in a graph, so that the path will be to one with th least number of edges. In order to write it, I used Dijkstra's algorithm with several modifications.

Is there any way to improve or modify my code?

#include<stdio.h>
#include<string.h>
#define INFINITY 9999
#define n 5
#define s 0
#define d 4

void Dijkstra(int Graph[n][n], int _n,int _s, int _d);

int main()
{
    int Graph[n][n]={{0,6,5,1,INFINITY},{6,0,3,INFINITY,INFINITY},{5,3,0,2,5},{1,INFINITY,2,0,6},{INFINITY,INFINITY,5,6,0}};

    Dijkstra(Graph,n,s,d);
    getchar();
    return 0;

}

void Dijkstra(int Graph[n][n], int _n,int _s, int _d)
{

    int distance[n],pred[n] ,visited[n],edge[n]={0},count,mindistance,nextnode=_s,i,j;

    //pred[] stores the predecessor of each node
    //count gives the number of nodes seen so far
    //edge[] stores the number of edged of every vertex's shortest path
      from the source

    //initialize pred[],distance[] and visited[]
    for(i=0;i<n;i++)
    {
        distance[i]=Graph[_s][i];
        pred[i]=_s;
        visited[i]=0;
        if(distance[i]>0 && distance[i]<INFINITY)
            edge[i]++;        //the neighbours of the source 
    }

    distance[_s]=0;
    visited[_s]=1;
    count=1;

    while(count<n-1 && nextnode!=_d )
    {
        mindistance=INFINITY;

        //nextnode gives the node at minimum distance
        for(i=0;i<n;i++)
            if(distance[i]<mindistance && !visited[i])
            {
                mindistance=distance[i];
                nextnode=i;

            }

            //check if a better path exists through nextnode            
            visited[nextnode]=1;

            if (nextnode!=_d)
            for(i=0;i<n;i++)
                if(!visited[i])
                {
                    if(mindistance+Graph[nextnode][i]<distance[i] )
                    {
                        distance[i]=mindistance+Graph[nextnode][i];

                        pred[i]=nextnode;
                        edge[i]=edge[nextnode]+1;

                    }

                    if(mindistance+Graph[nextnode][i]==distance[i] )
                    {
                        if(edge[i] >= edge[nextnode]+1)

                        {pred[i]=nextnode;

                        edge[i]=edge[nextnode]+1;
                        }
                    }
                }

                count++;
    }

    //print the path 

    i=nextnode;

printf("\n%d",_d);

j=_d;
do
{
  j=pred[j];
  printf("<-%d",j);
} while(j!=_s);

}
\$\endgroup\$
1
\$\begingroup\$

Naming

#define n 5
#define s 0
#define d 4

We normally use ALL_CAPS for preprocessor macros, to warn readers.

void Dijkstra(int Graph[n][n], int _n,int _s, int _d);

I'd prefer lower case for the function name and arguments (PascalCase is conventionally used for typedefs). The identifiers beginning with underscore are risky, because they are reserved for use by your compiler and standard library; also they don't tell us anything about their meaning. n seems to be the number of nodes; are s and d the start and target?

Separate the work from the I/O

At the moment, the Dijkstra() function both finds a route and prints it. Well-structured code separates these two activities, so you can do other things with the route. You'll need to define a suitable data structure to return for the route - you can start by filling in an array (remember to check bounds); perhaps move to a linked list or an allocated array.

Flexibility

At some stage, you'll want to move to supporting graphs of arbitrary size. For that, you're going to need to change n from constant to variable, and allocate and free storage for the distances. That will be worthy of its own review when you reach that stage.

\$\endgroup\$
0
\$\begingroup\$

This is a really useful algorithm to know, so it was a good choice to practice with! Here are some things I noticed.

Formatting Matters

As I was looking through your code, I thought I spotted a major error. At one of my first jobs I spent an entire day debugging a giant multi-screen for loop where the person who originally wrote it had use the loop control variable to control a different loop within the first one. Like this:

for (i = 0; i < max; i++)
{
    //... hundreds of lines of code
    for (i = min; i < other_max; i++)
    {
    }
    // ... hundreds more lines of code
}

That was about 20 years ago, and I haven't forgotten it. I thought I saw the same thing in your Dijkstra() function. Inside the while you have this for code:

    for(i=0;i<n;i++)
        if(distance[i]<mindistance && !visited[i])
        {
            mindistance=distance[i];
            nextnode=i;

        }

        //check if a better path exists through nextnode            
        visited[nextnode]=1;

        if (nextnode!=_d)
        for(i=0;i<n;i++)
            if(!visited[i])
            {
             // ... etc.

The way you've formatted it, it looks like you're making the same mistake, but you're not. And that's a problem. You should always put braces around your blocks of code in if, for, while, etc. statements. It's too easy to later make a mistake by attempting to add a line to the block, only to have it either always executed (if it's an if statement) or only executed once (if it's in a loop), causing very hard-to-find bugs.

If you aren't going to add the braces, at least format your code properly. It should look like this:

    for(i=0;i<n;i++)
        if(distance[i]<mindistance && !visited[i])
        {
            mindistance=distance[i];
            nextnode=i;

        }

     //check if a better path exists through nextnode            
     visited[nextnode]=1;

     if (nextnode!=_d)
     for(i=0;i<n;i++)
         if(!visited[i])
         {
         // ... etc.

Define Variables Where They Are First Used

You are declaring all the variables your function will use at the top of the function. That used to be a requirement in C many many years ago. It isn't any longer. Declaring a variable immediately before its first use is better, as it allows a reader to see that this is a new variable that wasn't previously set or modified, and it is easier to see its type.

I would also avoid declaring more than a single variable on a single line. Particularly in C where pointers have an odd syntax that leads to errors if not handled carefully. Had you done that, you might have noticed that you are declaring edge with a set of predefined values, but not visited even though they appear to need the same initialization.

Other Stuff

I would declare INFINITY to be larger than 9999. If you ever use this function with a large graph, you are likely to hit that limit. Make it something like INT_MAX.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.