Dijkstra’s shortest-path algorithm

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
Try Now – Data Structure MCQs