Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 5 / b

Take the directed graph with source $1$ and weighted edgesIt is a Directed acyclic graph, so has no negative-weight graph cycle. The true shortest path to $4$ is $1\to 3\to 2\to 4$, 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 $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.