= Solution
Take the <directed graph> with source $1$ and weighted <edges>
$$
1\to2:2,\qquad1\to3:5,\qquad3\to2:-4,\qquad2\to4:1.
$$
It is a <Directed acyclic graph>, so has no negative-weight <graph cycle>. The true <shortest path> to $4$ is $1\to3\to2\to4$, of weight $5-4+1=2$.
The standard <label-setting shortest-path algorithm> version of the <Dijkstra algorithm> extracts $1$, then $2$ at distance $2$, then $4$ at distance $3$, and only then $3$ at distance $5$. Thus it finalises \b[$d[4]=3$ instead of $2$]. Even if an implementation subsequently changes the stored label of the already settled vertex $2$, it does not reprocess its outgoing edge to $4$, so the error at $4$ remains. Allowing repeated reprocessing would instead be a <label-correcting shortest-path algorithm>, not the usual Dijkstra guarantee.
Back to article page
