Data Structure

# Dijkstra's Algorithm

Dijkstra's algorithm is a greedy algorithm that solves the shortest path problem for a directed graph G.
Dijkstra's algorithm solves the single-source shortest-path problem when all edges have non-negative weights.

### Dijkstra's Algorithm

```DIJKSTRA(G,s)
1 INITIALIZE-SINGLE-SOURCE(G, S)
2 S ← Ø
3 Q ← V[G]
4 while Q ≠ Ø
5 	do u ← EXTRACT-MIN(Q)
6 		S ← S U {u}
7 			for each vertex v ∈ Adj[u]
8				do if dist[v] > dist[u] + w(u,v)
9     				  then d[v] ←d[u] + w(u,v)
```
```INITIALIZE-SINGLE-SOURCE( Graph g, Node s )
dist[s] = 0;
for each vertex v in Vertices V[G] - s
dist[v] ← ∞
```

### Example

Step1

#### Consider A as source vertex

 No. of Nodes A B C D E Distance 0 10 3 ∞ ∞ Distance From A A

Step2

#### Now consider vertex C

 No. of Nodes A B C D E Distance 0 7 3 11 5 Distance From C C C C

Step3

#### Now consider vertex E

 No. of Nodes A B C D E Distance 0 7 3 11 0 Distance From C A C E

Step4

#### Now consider vertex B

 No. of Nodes A B C D E Distance 0 7 3 9 5 Distance From C A B C

Step5

#### Now consider vertex D

 No. of Nodes A B C D E Distance 0 7 3 9 11 Distance From A C A B C

A B C D E
0
A 0 10 3
C 7 3 11 5
E 14 5
B 9
D 16

### C FUNCTION of Dijkstra's Algorithm

```void dijikstra(int G[MAX][MAX], int n, int startnode)
{
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visited[MAX], count, mindistance, nextnode, i,j;
for(i=0;i < n;i++)
for(j=0;j < n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];

for(i=0;i< n;i++)
{
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count < n-1){
mindistance=INFINITY;
for(i=0;i < n;i++)
if(distance[i] < mindistance&&!visited[i])
{
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i < n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i] < distance[i])
{
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}

for(i=0;i < n;i++)
if(i!=startnode)
{
printf("\nDistance of %d = %d", i, distance[i]);
printf("\nPath = %d", i);
j=i;
do
{
j=pred[j];
printf(" <-%d", j);
}
while(j!=startnode);
}
}

```

### C IMPLEMETATION of Dijkstra's Algorithm

```#include<stdio.h>
#include<conio.h>
#define INFINITY 9999
#define MAX 10

void dijikstra(int G[MAX][MAX], int n, int startnode);

void main(){
int G[MAX][MAX], i, j, n, u;
clrscr();
printf("\nEnter the no. of vertices:: ");
scanf("%d", &n);
for(i=0;i < n;i++)
for(j=0;j < n;j++)
scanf("%d", &G[i][j]);
printf("\nEnter the starting node:: ");
scanf("%d", &u);
dijikstra(G,n,u);
getch();
}

void dijikstra(int G[MAX][MAX], int n, int startnode)
{
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visited[MAX], count, mindistance, nextnode, i,j;
for(i=0;i < n;i++)
for(j=0;j < n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];

for(i=0;i< n;i++)
{
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count < n-1){
mindistance=INFINITY;
for(i=0;i < n;i++)
if(distance[i] < mindistance&&!visited[i])
{
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i < n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i] < distance[i])
{
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}

for(i=0;i < n;i++)
if(i!=startnode)
{
printf("\nDistance of %d = %d", i, distance[i]);
printf("\nPath = %d", i);
j=i;
do
{
j=pred[j];
printf(" <-%d", j);
}
while(j!=startnode);
}
}

```