Dijkstra's Algorithm modification

An answer to this question on Stack Overflow.

Question

Let G (V, E) be a weighted, directed graph with non negative weight function W : E -> {0, 1, 2... W } for some non negative integer W . How to modify Dijkstra’s algorithm to compute the shortest paths from a given source vertex s in O(V W + E) time.

Answer

Standard Dijkstra's uses a priority queue and can handle floating-point values. This allows all the weights to differ from each other and implies no upper bound.

But now you have integer weights and an upper bound: given these additional constraints you should be able to build a faster algorithm. And, indeed, you can, by using buckets (one for each weight) to store the nodes.

In full:

  1. Create buckets labeled 0, 1, 2, 3, ..., W(V-1) where W is the maximum weight and V is the number of nodes. Bucket k will contain all nodes labeled with distance k. Each bucket can be represented by a vector or list of nodes.
  2. Buckets 0, 1, 2, ..., WV are checked sequentially until the first non-empty bucket is found. The nodes in this bucket are at the frontier.
  3. Each node in this bucket is labeled with its true distance and then deleted from the bucket.
  4. Steps (2-4) are now repeated (though begin scanning in 2 at the bucket you just emptied) until all buckets are empty.

You need WV buckets to account for the degenerate case in which W=1 but the graph is a line. In this case, the farthest apart two nodes can be is W(V-1).

A more complete explanation is available here.