Single Source Shortest Distance in a weighted graph
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#define N 9
void shortestPath(int graph[N][N], int n, int source)
{
int i,j;
int minDistance,minVertex;
int newDistance;
int* distance = (int*)malloc(n*sizeof(int));
for(i = 0; i < n; i++)
distance[i] = INT_MAX;
distance[source] = 0;
int* visited = (int*)malloc(n*sizeof(int));
for(i = 0; i < n; i++)
visited[i] = 0;
for(i = 0; i < n; i++)
{
minDistance = INT_MAX;
minVertex = -1;
for(j = 0; j < n; j++)
{
if (!visited[j]&&distance[j]<minDistance)
{
minDistance = distance[j];
minVertex = j;
}
}
visited[minVertex] = 1;
for(j = 0; j < n; j++)
{
if (!visited[j]&&graph[minVertex][j]!=0) {
newDistance = distance[minVertex] + graph[minVertex][j];
if (newDistance < distance[j])
distance[j] = newDistance;
}
}
}
for(i = 0; i < n; i++)
{
printf("Shortest distance from vertex %d to vertex %d: %d\n", source, i,
distance[i]);
}
}
int main()
{
int i,j;
int graph[N][N]={{0,4,0,0,0,0,0,8,0},
{4,0,8,0,0,0,0,11,0},
{0,8,0,7,0,4,0,0,2},
{0,0,7,0,9,14,0,0,0},
{0,0,0,9,0,10,0,0,0},
{0,0,4,14,10,0,2,0,0},
{0,0,0,0,0,2,0,1,6},
{8,11,0,0,0,0,1,0,7},
{0,0,2,0,0,0,6,7,0}};
shortestPath(graph,N,0);
return 0;
}
OUTPUT:
Shortest distance from vertex 0 to vertex 0: 0
Shortest distance from vertex 0 to vertex 1: 4
Shortest distance from vertex 0 to vertex 2: 12
Shortest distance from vertex 0 to vertex 3: 19
Shortest distance from vertex 0 to vertex 4: 21
Shortest distance from vertex 0 to vertex 5: 11
Shortest distance from vertex 0 to vertex 6: 9
Shortest distance from vertex 0 to vertex 7: 8
Shortest distance from vertex 0 to vertex 8: 14
