C Program to find Shortest Distances or Path using Dijkstra’s algorithm

By | 02.07.2017

Shortest Distances or Path using Dijkstra’s algorithm


Write a C Program to find Shortest Distances or Path using Dijkstra’s algorithm with Output. Here’s a simple Program to find Shortest Path or Distances using Dijkstra’s algorithm with output in C Programming Language.


Dijkstra’s Algorithm


Dijkstra’s algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph.

Algorithm Steps:

  • Set all vertices distances = infinity except for the source vertex, set the source distance = .
  • Push the source vertex in a min-priority queue in the form (distance , vertex), as the comparison in the min-priority queue will be according to vertices distances.
  • Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).
  • Update the distances of the connected vertices to the popped vertex in case of “current vertex distance + edge weight < next vertex distance”, then push the vertex
    with the new distance to the priority queue.
  • If the popped vertex is visited before, just continue without using it.
  • Apply the same algorithm again until the priority queue is empty.

Time Complexity: 

  • The time complexity of the above code/algorithm looks O(V^2) as there are two nested while loops. If we take a closer look, we can observe that the statements in inner loop are executed O(V+E) times (similar to BFS).
  • The inner loop has decreaseKey() operation which takes O(LogV) time. So overall time complexity is O(E+V)*O(LogV) which is O((E+V)*LogV) = O(ELogV)

Also Read : : C Program to find whether an Undirected Graph is Cyclic or not

Below is the source code for C Program to find Shortest Distances or Path using Dijkstra’s algorithm which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/* C Program to find Shortest Distances or Path using Dijkstra's algorithm */

#include<stdio.h>

#define MAX 100
#define TEMP 0
#define PERM 1
#define infinity 9999
#define NIL -1

void findPath(int s, int v );
void Dijkstra( int s);
int min_temp( );
void create_graph();

int n;    /* Denotes number of vertices in the graph */
int adj[MAX][MAX];
int predecessor[MAX];   /*predecessor of each vertex in shortest path*/
int pathLength[MAX];
int status[MAX];

int main()
{
        int s,v;

        create_graph();

        printf("\nEnter source vertex : ");
        scanf("%d",&s);

        Dijkstra(s);

        while(1)
        {
                printf("\nEnter destination vertex(-1 to quit): ");
                scanf("%d",&v);
                if(v == -1)
                        break;
                if(v < 0 || v >= n )
                        printf("\nThis vertex does not exist\n");
                else if(v == s)
                        printf("\nSource and destination vertices are same\n");
                else if( pathLength[v] == infinity )
            printf("\nThere is no path from source to destination vertex\n");
                else
                        findPath(s,v);
        }

        return 0;
}/*End of main()*/

void Dijkstra( int s)
{
        int i,current;

        /* Make all vertices temporary */
        for(i=0; i<n; i++)
        {
                predecessor[i] =  NIL;
                pathLength[i] = infinity;
                status[i] = TEMP;
        }
        /* Make pathLength of source vertex equal to 0 */
        pathLength[s] = 0;

        while(1)
        {
                /*Search for temporary vertex with minimum pathLength
                and make it current vertex*/
                current = min_temp( );

                if( current == NIL )
                        return;

                status[current] = PERM;

                for(i=0; i<n; i++)
                {
                        /*Checks for adjacent temporary vertices */
                        if ( adj[current][i] !=0 && status[i] == TEMP )
                                if( pathLength[current] + adj[current][i] < pathLength[i] )
                                {
                                        predecessor[i] = current;  /*Relabel*/
                                        pathLength[i] = pathLength[current] + adj[current][i];
                                }
                }
        }
}/*End of Dijkstra( )*/

/*Returns the temporary vertex with minimum value of pathLength
  Returns NIL if no temporary vertex left or
  all temporary vertices left have pathLength infinity*/
int min_temp( )
{
        int i;
        int min = infinity;
        int k = NIL;
        for(i=0;i<n;i++)
        {
                if(status[i] == TEMP && pathLength[i] < min)
                {
                        min = pathLength[i];
                        k = i;
                }
        }
        return k;
}/*End of min_temp( )*/


void findPath(int s, int v )
{
        int i,u;
        int path[MAX];          /*stores the shortest path*/
        int shortdist = 0;      /*length of shortest path*/
        int count = 0;          /*number of vertices in the shortest path*/

        /*Store the full path in the array path*/
        while( v != s )
        {
                count++;
                path[count] = v;
                u = predecessor[v];
                shortdist += adj[u][v];
                v = u;
        }
        count++;
        path[count]=s;

        printf("\nShortest Path is : ");
        for(i=count; i>=1; i--)
                printf("%d  ",path[i]);
        printf("\nShortest distance is : %d\n", shortdist);
}/*End of findPath()*/

void create_graph()
{
        int i,max_edges,origin,destin, wt;

        printf("\nEnter number of vertices : ");
        scanf("%d",&n);
        max_edges = n*(n-1);

        for(i=1;i<=max_edges;i++)
        {
                printf("\nEnter edge %d( -1 -1 to quit ) : ",i);
                scanf("%d %d",&origin,&destin);

                if( (origin == -1) && (destin == -1) )
                        break;

                printf("\nEnter weight for this edge : ");
                scanf("%d",&wt);

                if( origin >= n || destin >= n || origin<0 || destin<0)
                {
                        printf("\nInvalid edge!\n");
                        i--;
                }
                else
                        adj[origin][destin] = wt;
        }
}

OUTPUT : :


/* C Program to find Shortest Distances or Path using Dijkstra's algorithm */

Enter number of vertices : 6

Enter edge 1( -1 -1 to quit ) : 0 1

Enter weight for this edge : 2

Enter edge 2( -1 -1 to quit ) : 0 2

Enter weight for this edge : 5

Enter edge 3( -1 -1 to quit ) : 0 3

Enter weight for this edge : 1

Enter edge 4( -1 -1 to quit ) : 2 4

Enter weight for this edge : 3

Enter edge 5( -1 -1 to quit ) : 2 5

Enter weight for this edge : 2

Enter edge 6( -1 -1 to quit ) : 3 4

Enter weight for this edge : 1

Enter edge 7( -1 -1 to quit ) : 4 5

Enter weight for this edge : 5

Enter edge 8( -1 -1 to quit ) : -1 -1

Enter source vertex : 0

Enter destination vertex(-1 to quit): 1

Shortest Path is : 0  1
Shortest distance is : 2

Enter destination vertex(-1 to quit): 2

Shortest Path is : 0  2
Shortest distance is : 5

Enter destination vertex(-1 to quit): 3

Shortest Path is : 0  3
Shortest distance is : 1

Enter destination vertex(-1 to quit): 4

Shortest Path is : 0  3  4
Shortest distance is : 2

Enter destination vertex(-1 to quit): 5

Shortest Path is : 0  3  4  5
Shortest distance is : 7

Enter destination vertex(-1 to quit): -1

Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post…


Recommended Posts : :

5 1 vote
Article Rating
Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments