Dijkstra's Algorithm

Dijkstra's algorithm, also known as single-source shortest paths, solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It is a greedy algorithm and similar to Prim's algorithm. Algorithm starts at the source vertex, s, it grows a tree, T, that ultimately spans all vertices reachable from S. Vertices are added to T in order of distance i.e., first S, then the vertex closest to S, then the next closest, and so on.



									/*****Please include following header files*****/
// stdio.h
// limits.h
/***********************************************/

#define VERTICES_COUNT 9

static int MinimumDistance(int distance[], bool shortestPathTreeSet[])
{
	int min = INT_MAX;
	int minIndex = 0;

	for (int v = 0; v < VERTICES_COUNT; ++v)
	{
		if (shortestPathTreeSet[v] == false && distance[v] <= min)
		{
			min = distance[v];
			minIndex = v;
		}
	}

	return minIndex;
}

static void Print(int distance[])
{
	printf("Vertex    Distance from source\n");

	for (int i = 0; i < VERTICES_COUNT; ++i)
		printf("%d\t  %d\n", i, distance[i]);
}

static void Dijkstra(int graph[VERTICES_COUNT][VERTICES_COUNT], int source)
{
	int distance[VERTICES_COUNT];
	bool shortestPathTreeSet[VERTICES_COUNT];

	for (int i = 0; i < VERTICES_COUNT; ++i)
	{
		distance[i] = INT_MAX;
		shortestPathTreeSet[i] = false;
	}

	distance[source] = 0;

	for (int count = 0; count < VERTICES_COUNT - 1; ++count)
	{
		int u = MinimumDistance(distance, shortestPathTreeSet);
		shortestPathTreeSet[u] = true;

		for (int v = 0; v < VERTICES_COUNT; ++v)
			if (!shortestPathTreeSet[v] && graph[u][v] && distance[u] != INT_MAX && distance[u] + graph[u][v] < distance[v])
				distance[v] = distance[u] + graph[u][v];
	}

	Print(distance);
}


Example

									int graph[VERTICES_COUNT][VERTICES_COUNT] = {
	{ 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, 0, 10, 0, 2, 0, 0 },
	{ 0, 0, 0, 14, 0, 2, 0, 1, 6 },
	{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
	{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
};

Dijkstra(graph, 0);


Output

									Vertex    Distance from source
0         0
1         4
2         12
3         19
4         21
5         11
6         9
7         8
8         14