|
What is it?
Dijkstra's algorithm is a very efficient way of finding the shortest path from a source node to any other node in a graph. It does this by finding the shortest path from the source to every other node at once.
How it works:
Step 1: Initialize all nodes
Step 2: Repeatedly extract cheapest node and relax surrounding nodes
Step 1: Initialization
Initialization can be completed in O(n) time, where n is the number of nodes in the graph. Each node must be visited once to set its distance from the source to infinity. The source node is then updated to have distance of zero. The nodes of the graph are partitioned into two sets, with all nodes initially in the start set.
The data structure for one node might look like this:
----------------
NODE
ID
distfromS
predecessor
----------------
Step 2: Extract Cheapest and Relax
Find the "cheapest" node in the start set, meaning the node closest to the source node. The first time this step takes place, the source node will be the cheapest, since it is the only node with distance field equal to 0, while all the other nodes have been initialized to distance infinity.
There are some number of nodes adjacent to the cheapest node. For each of these adjacent nodes, examine its distance field to see whether an improvement can be made. Say, for instance, that u is currently the cheapest node and v is a node adjacent to u. Right now, the distance field of v says it is estimated to be 4 units away from the source node. The distance field for u says it is only one unit away from the source, and the distance from u to v is equal to one unit. By taking the path from the source through u to v, the total distance travelled is 1 + 1 or 2, which is an improvement over the previous estimate of 4. In this case, you would update the distance field for v to say that it is 2 units from the source, with u as its predecessor.
After you have processed every node adjacent to the cheapest node in this way, you are done with the cheapest node. Remove it from the start set and add it to the finish set, then start over again by finding a new cheapest node.
Results
When all nodes have been processed and the start set is empty, each node has information about the shortest path between the source and that node. It is possible to extract any one of the shortest paths by walking backwards from a node through it's predecessors until the source node is reached.
Complexity
The most worrisome part of Dijkstra's algorithm, in view of complexity, is the process of finding the cheapest node. The outer loop of the relaxation step takes O(n) time to complete, since each node is extracted once. Each time a node is extracted, each outgoing edge must be considered as adjacent nodes are examined. Although we do not know how many edges will be considered during a single iteration of the loop, we do know that each edge will be visited once total, which gives complexity O(m + n), where m is the number of edges and n is the number of vertices. The extraction of the cheapest node has still not been taken into account, however, and its cost depends largely on the data structure used to store the nodes. With linear storage, it would take time O(n) to find the cheapest node, which results in a total cost of time O(n^2). Improvements can be made on this time by using a Fibonacci heap to store the nodes, which allows extraction of the cheapest node in time O(log(n)). In this way, the best complexity attainable for Dijkstra's algorithm is O(m + nlog(n)).
|