Dijkstra's algorithm

Djikstra's algorithm 

•  solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the single-source shortest paths problem.
• This problem is related to the spanning tree one. The graph representing all the paths from one vertex to all the others must be a spanning tree - it must include all vertices. There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph,

G = (V,E)

where

V is a set of vertices and E is a set of edges.

Dijkstra's algorithm keeps two sets of vertices:

S		the set of vertices whose shortest paths from the source have already been determined and
V-	S :	the remaining vertices.

The other data structures needed are:

d :	array of best estimates of shortest path to each vertex
pi :	an array of predecessors for each vertex

The basic mode of operation is:

1. Initialise d and pi,
2. Set S to empty,
3. While there are still vertices in V-S,
1. Sort the vertices in V-S according to the current best estimate of their distance from the source,
2. Add u, the closest vertex in V-S, to S,
3. Relax all the vertices still in V-S connected to u

The  Algorithm is :

shortest_paths( Graph g, Node s )
    initialise_single_source( g, s )
    S := { 0 }        /* Make S empty */
    Q := Vertices( g ) /* Put the vertices in a PQ */
    while not Empty(Q) 
        u := ExtractCheapest( Q );
        AddNode( S, u ); /* Add u to S */
        for each vertex v in Adjacent( u )
            relax( u, v, w )

initialise_single_source( Graph g, Node s )
   for each vertex v in Vertices( g )
       g.d[v] := infinity
       g.pi[v] := nil
   g.d[s] := 0;

relax( Node u, Node v, double w[][] )
    if d[v] > d[u] + w[u,v] then
       d[v] := d[u] + w[u,v]
       pi[v] := u

Example

Given the following directed graph

Using vertex 5 as the source (setting its distance to 0), we initialize all the other distances to ∞.

Iteration 1: Edges (u₅,u₂) and (u₅,u₄) relax updating the distances to 2 and 4

Iteration 2: Edges (u₂,u₁), (u₄,u₂) and (u₄,u₃) relax updating the distances to 1, 2, and 4 respectively. Note edge (u₄,u₂) finds a shorter path to vertex 2 by going through vertex 4

Iteration 3: Edge (u₂,u₁) relaxes (since a shorter path to vertex 2 was found in the previous iteration) updating the distance to 1

Iteration 4: No edges relax

The final shortest paths from vertex 5 with corresponding distances is

CODE :-

Click here to download the program

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<stdbool.h>
struct vertex
{
int verName;
int d;
int pi;
bool isAvailable;
struct vertex *next;
}*headVertex=NULL;

int n;
int count;
addVer(int i,int flag)
{
struct vertex *ref;
ref=(struct vertex *)malloc(sizeof(struct vertex *));
ref->verName=i;
if(flag==0)
    {
        ref->d=INT_MAX;
    }
    else
    {
        ref->d=0;
    }
ref->pi=-1;
ref->isAvailable=true;
ref->next=NULL;
ref->next=headVertex;
headVertex=ref;
}
void printVer()
{
struct vertex *ref;
ref=headVertex;
while(ref!=NULL)
{
    printf("ver:%d \t dvalue: %d \t pivalue=%d \t isAvialble=%d\n",ref->verName,ref->d,ref->pi,ref->isAvailable);
ref=ref->next;
}
}
void addEdge(int graph[n][n])
{
int start,end,weight;
printf("START VER:");
scanf("%d",&start);
printf("END VER:");
scanf("%d",&end);
printf("WEIGHT:");
scanf("%d",&weight);
graph[start][end]=weight;
}
struct vertex * findMinVer()
{
    struct vertex *ref;
    ref=headVertex;
    int min=INT_MAX;
    struct vertex *minVer;
    minVer=headVertex;
    while(ref!=NULL)
    {
        if((ref->d <= min )&& ref->isAvailable==true)
        {
            minVer=ref;
            min=minVer->d;
        }
        ref=ref->next;
    }
    minVer->isAvailable=false;
   // printf("MIN VER:%d\n",minVer->verName);
    count--;
    return minVer;
}
struct vertex * findVer(int nm)
{
    struct vertex *ref=headVertex;
    while(ref!=NULL)
    {
        if(ref->verName==nm)
        {
            break;
        }
        ref=ref->next;
    }
    return ref;
}
void relax(struct vertex * u,struct vertex *v,int weight)
{
    if(v->d >(u->d)+weight)
    {
        v->d=u->d+weight;
        v->pi=u->verName;
    }
}
void findSssp(int graph[n][n],int src)
{
    int i,j=0;
    struct vertex * veru;
    veru=headVertex;
    struct vertex *q[n];
    while(count>0)
    {
       veru=findMinVer();
      // printVer();
       //printf("%d ",veru->verName);
       j=0;
       for (i=veru->verName;j<n;j++)
       {
            if(graph[i][j]>0)
            {
              //  printf("\tGRAPH[%d][%d]: %d\t",i,j,graph[i][j]);
                relax(veru,findVer(j),graph[i][j]);
            }

       }
    }
}
main()
{
int i,j,choise,src;
printf("ENTER THE NO. OF VERTICES IN THE GRAPH");
scanf("%d",&n);
int graph[n][n];
printf("ENTER THE SOURCE VERTICE FOR SSSP");
scanf("%d",&src);
count=n;
for(i=0;i<n;i++)
{
    if(i==src)
        {
            addVer(i,1);
        }
        else
        {
            addVer(i,0);
        }

}
printVer();
for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            graph[i][j]=0;
        }
    }
while(1)
{
printf("\nMENU:\n1-ADD EDGE\n2-FIND SSSP\n3-EXIT\n");
scanf("%d",&choise);
switch(choise)
{
case 1:addEdge(graph);break;
case 2:findSssp(graph,src);printVer();break;
case 3:exit(0);
}
}
}