Dijkstra's Algorithm modification

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 1

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.

Answer 2

I have once done research on this topic and the algorithm you're looking for is Dial algorithm. There is also further optimization of Dijkstra Algorithm, so I also attach it below. On the very bottom I put my tests on performance on those three algorithms.

Dial algorithm

Pseudocode

Efficient algorithm for small weights. Instead of a priority queue we use buckets for each weight from 0 to max weight. The complexity is O(m+n*C) where n is number of vertex, C is max cost, m is number of edges.

Another approach is Radix algorithm.

Radix heap

Pseudocode

Now, we have ln(C) of buckets. ith bucket stores edges in range [2^i, 2^(i+1)]. The complexity becomes O(m+nln(n*C)).

Tests

Test 1

Test 2

Test 3

Test 4