Find shortest paths to other vertices using Dijkra’s algorithm

What is Dijkstra’s Algorithm?

Dijkstra’s Algorithm is a popular graph traversal technique used to find the shortest path between nodes in a weighted graph. Developed by Edsger W. Dijkstra in 1956, this algorithm is a cornerstone in fields like computer networks, GPS navigation, artificial intelligence, and routing protocols.

Key Features of Dijkstra’s Algorithm

• Works on graphs with non-negative weights
• Provides single-source shortest path
• Efficient for sparse graphs
• Commonly implemented using a priority queue or min-heap

How Does Dijkstra’s Algorithm Work?

• Initialize distances: Set the distance to the source node as 0 and all others as ∞.
• Visit the unvisited node with the smallest tentative distance.
• Update the distances of neighboring nodes.
• Mark the node as visited (processed).
• Repeat until all nodes are visited or the shortest path is found.

Step-by-Step Example

Consider a graph with nodes A, B, C, D, and E. Suppose you need the shortest path from A to E. Dijkstra’s algorithm will evaluate all possible paths, minimize the total weight, and return the optimal path with the least cost.

Pseudocode of Dijkstra’s Algorithm

function Dijkstra(Graph, source):
create vertex set Q
for each vertex v in Graph:
dist[v] ← ∞
prev[v] ← undefined
add v to Q
dist[source] ← 0

while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q

for each neighbor v of u:
alt ← dist[u] + length(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]

 Real-Life Applications of Dijkstra’s Algorithm

• GPS systems: Finding the shortest route between locations
• Computer networks: Optimizing routing paths (e.g., OSPF)
• AI & Games: Pathfinding for characters and units
• Logistics & Delivery: Optimizing delivery routes

 Time and Space Complexity

• Time Complexity: Using min-heap (priority queue): O((V + E) log V)
• Space Complexity: O(V)

Find shortest paths to other vertices using Dijkra’s algorithm

#include<stdio.h>
#include<conio.h>
#define INFINITY 99

void dijktra(int);
void printpath(int);
int MinVertex();
int dist[10],p[10], Visit[10];
int wt[10][10], n, edge;

void main()
{
int i,j,s;
clrscr();
printf("\n Enter the number of vertices in a graph: ");
scanf("%d", &n);
for(i=1; i<=n;i++)
{
dist[i] = 0;
p[i] = 0;
Visit[i] = 0;
}
printf("\n Enter the weight matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d", &wt[i][j]);
printf("\n Enter the source vertex: ");
scanf("%d", &s);
printf("\n\n Shortest paths from vertex %d are : \n\n", s);
dijktra(s);
printpath(s);
getch();
}

void dijktra(int s)
{
int i, i, step, u;
for(i=1; i<=n; i++)
{
dist[i] = wt[s][i];
if(dist[i] == INFINITY)
p[i] = 0;
else
p[i] = 0;
}
Visit[s] = 1;
dist[s] = 0;
for(step=2; step<=n; step++)
{
u = MinVertex();
Visit[u] = 1;
for(j=1; j<=n; j++)
if(((dist[u]+wt[u][i]) < dist[j]) && !Visit[j])
{
dist[j] = dist[u] + wt[u][j];
p[j] = u;
}
}
}

int MinVertex()
{
int min= INFINITY;
int u, i;
for(i=1;i<=n;i++)
{
if((dist[i]<min) && (Visit[i] == 0))
{
min = dist[i];
u = i;
}
}
return u;
}

void printpath(int s)
{
int i, t;
for(i=1;i<=n;i++)
if(Visit[i] == 1 && i!=s)
{
printf("Vertex->%d length: %d path:",i,dist[i]);
t = p[i];
printf("%d", i);
while(t != s)
{
printf("<--%d", t);
t = p[t];
}
if(t == s)
prinrf("<--%d\n", s);
}
}

OUTPUT
Enter the number of vertices in graph: 4

Enter the weighted matrix:
0 2 1 4
2 0 5 1
1 5 0 2
4 1 2 0

Enter the source vertex: 2
Shortest paths from the vertex 2 are:

Vertex -> 1 length: 2 path: 1<--2
Vertex-> 3 length:3 path:3<--4<--2
Vertex->4 length: 1 path: 4<--2