Dijkstra's Algorithm

dijkstra.c

void dijkstra(int short[ ], int adjM[ ] [SIZE], int previous[SIZE]) 
{
	int i, k, mini, n = SIZE;
	int visited[SIZE]; 
	for (i = 0; i < n; ++i) 
	{
		short[i] = INFINITY;
		visited[i] = 0; 	/* the i-th element has not yet been visited */
	}
	short[0] = 0;  previous[0] = -1;	//  no previous vertex
	for (k = 1; k < n; ++k) 
	{
		mini = -1;
		for (i = 0; i < n; ++i)‏
			if (!visited[i] && ((mini == -1) || (short[i] < short[mini])))‏
				mini = i;		//  nearest unvisited vertex
		visited[mini] = 1;
		for (i = 1; i < n; ++i)‏
			if (adjM[mini][i] != 0)	//  if connected
				if (short[mini] + adjM[mini][i] < short[i]) 	//  shorter via
				{	short[i] = short[mini] + adjM[mini][i];	//  vertex mini
		//  extra code		previous[i] = mini;		}
	}
}

Each step in the algorithm finds the next vertex in the shortest path so far.
Thus, at the kth step, we have found the shortest path for k vertices.

So we can represent the shortest path to vertex x, by finding
the shortest path from the previous vertex.