Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$

Answered By : Neal Young

If edge weights are integers in $\{0,1,\ldots,K\}$, you can implement Dijkstra's to run in $O(K|V|+|E|)$ time, following @rrenaud's suggestion. Here is a more explicit explanation.

At any time, the (finite) keys in the priority queue are in some range $\{D,D+1,\ldots,D+K\}$, where $D$ is the value of the last key removed from the priority queue. (Every key is at least $D$, because the sequence of keys removed by Dijkstra's algorithm is non-decreasing, and every key is at most $D+K$, because every key has value $d[u] + wt(u,w)$ for some edge $(u,w)$ where $d[u]$ is the distance from the source to some vertex $u$ that has already been removed, so $d[u]\le D$.)

Because of this, you can implement the priority queue with a circular array $A[0..K]$ of size $K+1$, with each cell containing a bucket. Store each vertex with key $k$ in the bucket in cell $A[h(k)]$ where $h(k)=k \bmod (K+1)$. Keep track of $D$. Do operations as follows:

• delete-min: While $A[h(D)]$ is empty, increment $D$. Then delete and return a vertex from $A[h(D)]$.

• insert with key $k$: Add the vertex to the bucket of $A[h(k)]$.

• decrease-key $k$ to $k'$: Move the vertex from $A[h(k)]$ to $A[h(k')]$.

Insert and decrease-key are constant-time operations, so the total time spent in those operations will be $O(|V|+|E|)$. The total time spent in delete-min will be $O(|V|)$ plus the final value of $D$. The final value of $D$ is the maximum (finite) distance from the source to any vertex (because a delete-min that takes $i$ iterations increases $D$ by $i$). The maximum distance is at most $K(|V|-1)$ because each path has at most $|V|-1$ edges. Thus, the total time spent by the algorithm is $O(K|V|+|E|)$.

Problem Detail: 

Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the algorithm / data structure and improve the time complexity to $O(|V|+|E|)$?

Asked By : user1675999

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6797