Dijkstra’s algorithm finds the shortest paths from a given node to all other nodes in a graph
- Initially,
Mark the given node as known (path length is zero)For each out-edge, set the distance in each neighboring node equal to the cost (length) of the out-edge, and set its predecessor to the initially given node - Repeatedly (until all nodes are known),
Find an unknown node containing the smallest distance
Mark the new node as known
For each node adjacent to the new node, examine its neighbors to see whether their estimated distance can be reduced (distance to known node plus cost of out-edge)
If so, also reset the predecessor of the new node
Analysis of Dijkstra’s algorithm
Assume that the average out-degree of a node is some constant k
Initially,Mark the given node as known (path length is zero)
This takes O(1) (constant) time
For each out-edge, set the distance in each neighboring node equal to the cost (length) of the out-edge, and set its predecessor to the initially given node
If each node refers to a list of k adjacent node/edge pairs, this takes O(k) = O(1) time, that is, constant time
Notice that this operation takes longer if we have to extract a list of names from a hash table,
Repeatedly (until all nodes are known), (n times)
Find an unknown node containing the smallest distance
Probably the best way to do this is to put the unknown nodes into a priority queue; this takes k * O(log n) time each time a new node is marked “known” (and this happens n times)
Mark the new node as known — O(1) time
For each node adjacent to the new node, examine its neighbors to see whether their estimated distance can be reduced (distance to known node plus cost of out-edge)
If so, also reset the predecessor of the new node
There are k adjacent nodes (on average), operation requires constant time at each, therefore O(k) (constant) time
Combining all the parts, we get:
O(1) + n*(k*O(log n)+O(k)), that is, O(nk log n) time
