Data Structure: Unit IV : Multiway Search Trees and Graphs

Finding Shortest Path

Operations, Algorithm with Example C Programs | Graphs | Data Structure

Home | All Subjects | CSE Department | Data Structure

Dijkstra's Algorithm is a popular algorithm for finding shortest path.

Finding Shortest Path

•Dijkstra's Algorithm is a popular algorithm for finding shortest path.

• This algorithm is called single source shortest path algorithm because in this algorithm, for a given vertex called source the shortest path to all other vertices is obtained.

• This algorithm applicable to graphs with non-negative weights only.

Ex. 5.14.1 Obtain the shortest path for the given graph.

Sol. Now we will consider each vertex as a source and will find the shortest distance from this vertex to every other remaining vertex. Let us start with vertex A.

Thus the shortest distance from A to E is obtained.

that is A-B-C-E with path length = 4 +1+3 = 8 obtained by choosing appropriate source and destination.

Ex. 5.14.2 Using Dijkstra's algorithm find the shortest path from the source node A

Sol. The source node S={A}, the target nodes

P =(B, E, H, C, D}

Step 1: S = {A}

P = {B, E, H, C, D}

d(A, B)=2

d (A, H) = 4

d. (A, D) =∞

d(A, E)=5

d (A, C) = ∞

The minimum distance is 2. Hence choose vertex B.

Step 2:

S {A, B}

d(A, E) = 5

d(A, H)=4

P = {E, H, C, D}

d(A, C) = 2 + 5 = 7

d (A, D)=∞

The minimum distance is 4. It is obtained from vertex H. Choose vertex H.

Step 3:

S={A, B, H}

d (A, E)=5.

P = {E, C, D}

d (A, C) = 4+2 = 6

d (A, D) = ∞

Choose vertex E

Step 4:

S ={A, B, H, E}

P = {C, D}

d(A, C)=6

choose vertex C

d(A, D) = 5+3=8

Step 5:

S={A, B, H, E, C}

P = {D}

d (A, D) = 8

choose vertex D.

S={A, B, H, E, C, D}

Thus the shortest paths from single source S is as given below

Ex. 5.14.3 Implementation of Shortest Path Algorithm (Application of Graph)

Sol. :

#include<stdio.h>

#include <conio.h>

#define infinity 999

int path[10];

void main()

{

int tot_nodes,i,j,cost[10][10],dist[10],s[10];

void create(int tot_nodes,int cost[][10]);

void Dijkstra(int tot_nodes,int cost[][10], int i,int dist[10]);

void display(int i,int j,int dist[10]);

clrscr();

printf("\n\t\t Creation of graph ");

printf("\n Enter total number of nodes ");

scanf("%d", &tot_nodes);

create(tot_nodes,cost);

for(i=0;i<tot_nodes;i++)

{

printf("\n\t\t\t Press any key to continue...");

printf("\n\t\t When Source = %d\n",i);

for(j=0;j<tot_nodes;j++)

{

Dijkstra (tot_nodes, cost,i,dist);

if(dist[j]==infinity)

printf("\n There is no path to %d\n",j);

else

{

display(i,j,dist);

}

void create(int tot_nodes,int cost[][10])

{

int i,j,val,tot_edges,count=0;

for(i=0;i<tot_nodes;i++)

{

for(j=0;j<tot_nodes;j++)

{

if(i==j)

cost[i][j]=0;//diagonal elements are 0

else

cost[i][j]=infinity;

}

printf("\n Total number of edges");

scanf("%d", &tot_edges);

while(count<tot_edges)

{

printf("\n Enter Vi and Vj");

scanf("%d %d", &i,&j);

printf("\n Enter the cost along this edge");

scanf("%d",&val);

cost [j][i]=val;

cost[i][j]=val;

count++;

}

void Dijkstra (int tot_nodes,int cost [10][10], int source,int dist[])

{

int i,j,v1,v2,min_dist;

int s[10];

for(i=0;i<tot_nodes;i++)

{

dist[i]=cost [source][i];//initially put the

s[i]=0; //distance from source vertex to i

//i is varied for each vertex

path[i]=source;//all the sources are put in path

}

s[source]=1;

for(i=1;i<tot_nodes;i++)

{

min_dist=infinity;

v1=-1;//reset previous value of v1

for(j=0;j<tot_nodes;j++)

{

if(s[j]==0)

{

if(dist[j]<min_dist)

{

min_dist=dist[j];//finding minimum distance

v1=j;

}

s[v1]=1;

for(v2=0;v2<tot_nodes;v2++)

{

if(s[v2]==0)

{

if(dist[v1]+cost [v1][v2] <dist[v2])

{

dist[v2]=dist[v1]+cost[v1][v2];

path[v2]=v1;

}

void display(int source,int destination,int dist[])

{

int i;

getch();

printf("\n Step by Step shortest path is...\n");

for(i=destination;i!=source;i=path[i])

{

printf("%d <-",i);

}

printf("%d",i);

printf(" The length=%d",dist[destination]);

}

Output

Creation of graph

Enter total number of nodes 5

Total number of edges 7

Enter Vi and Vj 0 1

Enter the cost along this edge 4

Enter Vi and Vj 0 2

Enter the cost along this edge 8

Enter Vi and Vj 1 2

Enter the cost along this edge 1

Enter Vi and Vj 1 3

Enter the cost along this edge 3

Enter Vi and Vj 2 3

Enter the cost along this edge 7

Enter Vi and Vj 2 4

Enter the cost along this edge 3

Enter Vi and Vj 3 4

Enter the cost along this edge 8

Press any key to continue...

When Source =0

Step by Step shortest path is....

0 The length=0