Breadth-first search treats all edges as having the same length. This is rarely true in applications where shortest paths are to be found. For instance, suppose you are driving from San Francisco to Las Vegas, and want to find the quickest route. The figure below shows the major highways you might conceivably use. Picking the right combination of them is a shortest-path problem in which the length of each edge (each stretch of highway) is important.

We annotate every edge

Breadth-first search finds shortest paths in any graph whose edges have unit length. Can we
adapt it to a more general graph *positive integers*?

Here is a simple trick for converting

For any edgeGraph$e = (u, v)$ of$E$ , replace it by$l_e$ edges of length$1$ , by adding$l_e − 1$ dummy nodes between$u$ and$v$ .

If efficiency were not an issue, we could stop here. But when

To see this more concretely, consider the graphs *interesting* is happening—specifically, whenever one of the real nodes
(from the original graph

We do this by setting two alarms at the outset, one for node

More generally, at any given moment the breadth-first search is advancing along certain
edges of

The following “alarm clock algorithm” faithfully simulates the execution of BFS on

- Set an alarm clock for node
$s$ at time$0$ . - Repeat until there are no more alarms:

Say the next alarm goes off at time$T$ , for node$u$ . Then:- The distance from
$s$ to$u$ is$T$ . - For each neighbor
$v$ of$u$ in$G$ :- If there is no alarm yet for
$v$ , set one for time$T + l(u, v)$ . - If
$v$ ’s alarm is set for later than$T + l(u, v)$ , then reset it to this earlier time.

- If there is no alarm yet for

- The distance from

The alarm clock algorithm computes distances in any graph with positive integral edge lengths. It is almost ready for use, except that we need to somehow implement the system of alarms. The right data structure for this job is a priority queue (usually implemented via a heap), which maintains a set of elements (nodes) with associated numeric key values (alarm times) and supports the following operations:

*Insert*. Add a new element to the set.*Decrease-key*. Accommodate the decrease in key value of a particular element. (The name decrease-key is standard but is a little misleading: the priority queue typically does not itself change key values. What this procedure really does is to notify the queue that a certain key value has been decreased.)*Delete-min*. Return the element with the smallest key, and remove it from the set.*Make-queue*. Build a priority queue out of the given elements, with the given key values. (In many implementations, this is significantly faster than inserting the elements one by one.)

The first two let us set alarms, and the third tells us which alarm is next to go off. Putting this all together, we get Dijkstra’s algorithm.

In the code,

In summary, we can think of Dijkstra’s algorithm as just BFS, except it uses a priority queue instead of a regular queue, so as to prioritize nodes in a way that takes edge lengths into account. This viewpoint gives a concrete appreciation of how and why the algorithm works, but there is a more direct, more abstract derivation that doesn’t depend upon BFS at all. We now start from scratch with this complementary interpretation.

Here’s a plan for computing shortest paths: expand outward from the starting point *the node outside $R$ that is closest to $s$*. Let us call this node

To answer, consider

*Since we are assuming that all edge lengths are positive*, *a known shortest path extended by a single edge*.

But there will typically be many single-edge extensions of the currently known shortest
paths; which of these identifies

The answer is, the shortest of these extended
paths. Because, if an even shorter single-edge-extended path existed, this would once more
contradict

We now have an algorithm for growing

Incorporating priority queue operations gives us back Dijkstra’s algorithm.

To justify this algorithm formally, we would use a proof by induction, as with breadth-first search. Here’s an appropriate inductive hypothesis.

At the end of each iteration of the while loop, the following conditions hold: (1) there is a valueThe base case is straightforward (with$d$ such that all nodes in$R$ are at distance$\le d$ from$s$ and all nodes outside$R$ are at distance$\ge d$ from$s$ , and (2) for every node$u$ , the value$dist(u)$ is the length of the shortest path from$s$ to$u$ whose intermediate nodes are constrained to be in$R$ (if no such path exists, the value is$\infty$ ).

At the level of abstraction of pseudocode above, Dijkstra’s algorithm is structurally identical to
breadth-first search. However, it is slower because the priority queue primitives are
computationally more demanding than the constant-time

The running time of Dijkstra’s algorithm depends heavily on the priority queue implementation used. Here are the typical choices.

Implementation | |||

Array | |||

Binary heap | |||

Fibonacci heap |

So for instance, even a naive array implementation gives a respectable time complexity
of

This depends on whether the graph is sparse (has few edges) or dense (has lots of them).
For all graphs,

The

The last line in the table gives running times using a sophisticated data structure called
a Fibonacci heap. Although its efficiency is impressive, this data structure requires
considerably more work to implement than the others, and this tends to dampen its appeal in
practice. We will say little about it except to mention a curious feature of its time bounds.
Its *amortized* cost of heap

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.