Dijkstra's algorithm for edge weights in range 0, ..., W
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] &lt;- {}, 0 &lt;= i &lt;= C
L[inf] &lt;- {}
L[0] &lt;- {s}

for v in V do
    push v into L[inf]
    d[v] &lt;- inf
end

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