Learning About the Graph Construct using Games, Part II - Dijkstra's algorithm
(Page 2 of 5 )
Okay, here is the deal: we have a graph; the edges are weighted. You are given a node, and you want to find the shortest path from this node to all other nodes. The path length is the sum of weights of all edges on this path. (If edges are not weighted, you can assume that every edge has a weight of one, and in this case, the shortest path is the one with the fewest number of edges on it).
How can you solve this problem? I encourage you to think about it for a second. How many ideas would you come up with? How many of them actually work?
Anyway, here is the idea Dijkstra came up with…
Preparation step:
Dijkstra's algorithm uses three additional arrays. The three arrays have a number of elements equal to the number of nodes in the graph.
The first array (let's call it isVisited[]) is a boolean array, and it keeps track of which nodes have been reached.
The second array (let's call it distance[]) is an integer array, and it keeps track of the minimum distances from the start node to every node in the graph.
At the beginning, the isVisited array starts with all false, except for the entry of the start node, which is set to true.
The distance array initially starts with
- a zero in the entry of the start node (This is the distance from the starting node to itself).
- infinity for any node that you can't reach immediately from the start node (a very big integer will do).
- the edge weight for any node that you can reach immediately from the start node.
The third array is called the previous[]. For every node, this array holds the node immediately previous to it in the shortest path. The initial value for this array the index of the start node.
For example, for this graph, if we are trying to find shortest paths starting at node A…
The three arrays will start like this…
The only interesting one is the distance array. The first entry is 0 since a is the initial node itself. The last two entries are 5 and 12 since a is connected to both e and f, and the edges have these weights. a is not connected to any other nodes, so they are all set to 
.
Algorithm steps:
- Select the node with the smallest distance (in the distance array), that has not been visited before (isVisited is false). Let's call this node X.
- Set its visited status to true.
- For every node Y that has not been visited yet, see if it is better to go from the start node to X, and then from X to Y. If it is better than the current entry in the distance array, update the distance array, and make sure that the previous of Y is set to X.
- If there are still more unvisited nodes, go back to 1
See, it is a piece of cake! What? It is not? Okay, let me explain.
Basically, Dijkstra's algorithm divides the nodes into two sets. These are the nodes that we have already reached (we now know the shortest path to), and the nodes we have not yet reached (we don't know the shortest path to). Initially, the only node we know the path to is the initial node (we don't even have to move to reach it, do we?); all other nodes are still in the other set.
With every step, we select the node that is nearest to the initial node. Since it is the nearest to the initial node, the path to it is the shortest path to this node. We mark it as visited, and then we do a very important step: for all the remaining unvisited nodes, we check to see if going from the starting node to the newly visited node, and then to this node, makes any improvements. If it does, we update the distance array for the corresponding node.
Next: Algorithm in action >>
More Development Cycles Articles
More By Mohamed Saad
