Djikstra's algorithm

Concept

Djikstra's algorithm finds the shortest path from the source vertex to the destination vertex.

Let  source vertex = 1 , destination vertex = 6

Blue    ---> current vertex

Yellow ---> visited vertices

Let cost of source vertex be 0 and cost of other vertices be infinity.

Then cost of a vertex (say v) is calculated by the formula

cost(v) = min(cost(current vertex)+edge_cost(current vertex,v) , previous_cost(v))

We stop when we arrive to destination vertex.

Terms

cost matrix : Associate each edge with cost.Suppose there is an edge between i--j then 

cost_mat[i][j] = cost_mat[j][i] = cost of edge(i--j)

Suppose there is no edge between i--j then

cost_mat[i][j] = cost_mat[j][i] =  ∞ 

from[] : Cost is calculated from which vertex.

from[3] = 1 means cost is calculated from vertex 1 to 3.

cost[] : Cost from a particular vertex.

cost[3] = 2 & from[3] = 1 means cost(3) = cost(1)+edge_cost(1,3)

Algorithm

1.Make an arbitrary vertex(v) as current.
  Mark current vertex as visited.(vis[v]=1)
  Update cost[i]
         from[i] (current vertex)
         initialize vis[i]=0 where v≠i

  Taking only unvisited vertices into account,

2.Find min cost in cost[].Make that vertex as current and mark it visited.Stop 
  if current vertex is the destination vertex.

3.For all neighbouring vertices of current,calculate their new costs.Check if 
  newly calculated cost is lesser than previous cost.
  If yes then 
                      Update cost[i]
                      Update from[i] (current vertex) 

4.Repeat from 2 until all vertices are visited.

Code

void djikstra()
{
    int start,dest = n,min_cost,curr,i,j;

    printf("\nEnter starting vertex ");
    scanf("%d",&start);

    vis[start]=1;

    for(i=1;i<=n;i++)
    {
        if(i!=start)
        {
            vis[i]=0;
            from[i]=start;
            cost[i]=cost_mat[start][i];
        }
    }

    for(i=1;i<n;i++)
    {
        min_cost = 999;

        for(j=1;j<=n;j++)                                   //min cost in cost[]
        {
            if(vis[j]==0 && cost[j]<min_cost)
            {
                min_cost = cost[j];
                curr = j;
            }
        }       

        vis[curr]=1;

        if(curr==dest)
            break;

        for(j=1;j<=n;j++)                           //update cost[],from[]
        {
            if(vis[j]==0 && (cost_mat[curr][j]+min_cost) < cost[j])
            {
                from[j] = curr;
                cost[j] = cost_mat[curr][j]+min_cost;
            }
        }
    }

    //Shortest Path from start--dest

    printpath(start,dest);          

    printf("\nMin cost = %d",cost[dest]);
}

void printpath(int start,int dest)
{
    if(dest==start)
    {
        printf("%d  ",start);
        return;
    }

    printpath(start,from[dest]);

    printf("%d  ",dest);
}

Code Tracing

Let  source vertex = 1 , destination vertex = 6

 Vertices        1     2     3     4     5     6

    vis[]        1     0     0     0     0     0
   cost[]        -     6     2     5     ∞     ∞
   from[]        -     1     1     1     1     1                     curr = 1

    vis[]        1     0     1     0     0     0
   cost[]        -     6     2     4     3    11
   from[]        -     1     1     3     3     3                     curr = 3

    vis[]        1     0     1     0     1     0
   cost[]        -     6     2     4     3     8
   from[]        -     1     1     3     3     5                     curr = 5

    vis[]        1     0     1     1     1     0
   cost[]        -     6     2     4     3     8
   from[]        -     1     1     3     6     5                     curr = 4

    vis[]        1     1     1     1     1     0
   cost[]        -     6     2     2     3     7
   from[]              1     1     3     6     2                     curr = 2

    vis[]        1     1     1     1     1     1
   cost[]        -     6     2     2     3     7
   from[]              1     1     3     6     2                     curr = 6

Printing the shortest path from source (1) to destination (6)

from[] has stored the vertex from which you found the shortest path to a particular vertex.Now you just need to backtrack from destination vertex.
from[6] = 2
from[2] = 1 Stop as we arrived at source vertex.

So the shortest path is 1 -- 2 -- 6

As we need to print the path from source to destination,we have used recursion.

O/P