**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**