Example:
#include <stdio.h>
#include <conio.h>
#define INFINITY 9999
#define MAX 10
void
Dijkstra(int G[MAX][MAX], int n, int startnode);
int main()
{
int G[MAX][MAX], i, j, n, u;
printf("Enter Number of Nodes:->");
scanf("%d", &n);
printf("\nEnter Adjacency Matrix:-->\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &G[i][j]);
}
}
printf("\nEnter Initial Node:-->");
scanf("%d", &u);
Dijkstra(G, n, u);
return 0;
}
void Dijkstra(int G[MAX][MAX], int n, int startnode)
{
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visited[MAX], count, mindistance, nextnode, i, j;
// create cost matrix
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];
}
}
}
// initialize pred[],distance[] and visited[]
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;
// nextnode gives the node at minimum distance
for (i = 0; i < n; i++)
if (distance[i] < mindistance && !visited[i])
{
mindistance = distance[i];
nextnode = i;
}
// check if a better path exists through nextnode
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++;
}
// print the path and distance of each node
for (i = 0; i < n; i++)
if (i != startnode)
{
printf("\nDistance of node %d=%d", i, distance[i]);
printf("\nPath =%d", i);
j = i;
do
{
j = pred[i];
printf("<-%d", j);
} while (j != startnode);
}
}