patternMinor

Dijkstra's algorithm for edge weights in range 0, ..., W

Submitted by: @import:stackexchange-cs·Mar 10, 2026·

Viewed 0 times

algorithm-analysis shortest-path cs data-structures algorithms stackoverflow weighted-graphs

dijkstrarangeweightsedgealgorithmfor

Problem

Suppose I want to run Dijkstra's algorithm on a graph whose edge weights are integers in the
range 0, ..., W, where W is a relatively small number.
How can I modify that algorithm so that it takes time just O((|V| + |E|) logW) and relatively easy implement that in C/C++?

Solution

This is the algorithm I know of that is $\mathcal{O}(|E| + W|V|)$. Some things to note:

$C$ is defined as the maximum cost of any shortest path that leaves $s$ (the source). It is at most $W|V|$.

Each $L[i]$ is a doubly-linked list. The $L[i]$ keep track of all vertices that are currently at distance $i$ from the source.

$d[v]$ is the shortest distance (so far) from the source to vertex $v$

Each edge and vertex of the graph will be visited only once, and the outer loop runs in time $\mathcal{O}(C)$, therefore the complexity of the algorithm is $\mathcal{O}(|E| + |V| + C)$. Since $C \leq W|V|$, this reduces to $\mathcal{O}(|E| + W|V|)$.

L[i]  d[v] + w(v, u) do
            remove u from L[d[u]]
            d[u] <- d[v] + w(v, u)
            push u in L[d[u]]
        end
    end
    p <- p + 1
end

Code Snippets

L[i] <- {}, 0 <= i <= C
L[inf] <- {}
L[0] <- {s}

for v in V do
    push v into L[inf]
    d[v] <- inf
end

d[s] <- 0
p <- 0
while p < C do
    while L[p] != {} do
        pop v from L[p]
        for (v, u) with d[u] > d[v] + w(v, u) do
            remove u from L[d[u]]
            d[u] <- d[v] + w(v, u)
            push u in L[d[u]]
        end
    end
    p <- p + 1
end

Context

StackExchange Computer Science Q#19252, answer score: 3

Revisions (0)

No revisions yet.