Dijkstra’s Algorithm

Given a network of cities and the distances between them,the task is to find the shortest path from a city(source) to all other cities connected to it.The network of cities with their distances is represented as a weighted digraph.It is also known as single-source,shortest path problem.

Algorithm-

N is the number of vertices labeled {0,1,2,3….N-1} of the weighted digraph.cost[0:N-1][0:N-1] is the cost matrix of the graph.If there is no edge from i to j,then cost[i][j]=INT_MAX.If i equals j,then cost[i][j]=0.
Vertex 0 is the source.
V is the set of N cities
T={0}; //T is initialized by adding the source vertex

//distance[] is initialized to the cost of the edges connecting vertex i with the source vertex 0.
for(i=1 to N)
{
distance[i]=cost(0,i);
}

for(i=0 to N-2)
{
Choose a vertex u in V-T such that distance[u] is a minimum;
Add u to T;

for each vertex w in V-T
{
distance[w]=minimum(distance[w],distance[u]+cost[u,w]);
}
}

Its time complexity is O(N^2) where N is the number of cities.

Code-


for(i=0;i<n;i++)
    {
     b[i]=0;
     distance[i]=cost[0][i];
    }
//b[i]=1 if i is in set T and b[i]=0 if it is in set V-T.

    b[0]=1;//T is initialized
    z=1;//counter initialized to 1

    while(z!=n)
    {
    min=INT_MAX;
    
    for(i=0;i<n;i++)
    {
                    if((b[i]==0)&&(distance[i]<min))
                    {
                       min=distance[i];
                       u=i;
                    }
    }
                    b[u]=1;
                    z++;
    for(w=0;w<n;w++)
 {
    if((cost[u][w]!=0) && (b[w]==0) && (distance[u]!=INT_MAX) && (distance[u]+cost[u][w]<distance[w]))
{
   distance[w]=distance[u]+cost[u][w];
}
 }

    }

//printing the shortest distances
for(i=0;i<n;i++)
printf("%d ",distance[i]);


Example-

If the cost matrix is-

@ denotes INT_MAX

0 20 @ 40 110
@ 0 60 @ @
@ @ 0 @ 20
@ @ 30 0 70
@ @ @ @ 0

The output is-

distance[0]=0
distance[1]=20
distance[2]=70
distance[3]=40
distance[4]=90

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

44,588 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>