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

You may be interested in:
Data Structures and Algorithms – MCQs.
Data Structures and Algorithms Online Tests