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

No: equal-length shortest paths permit different trees. Consider edges $s\to a,s\to b,a\to t,b\to t$, all of weight one. Both routes to $t$ have length two. A shortest-path tree may therefore choose either $a$ or $b$ as the predecessor of $t$.

The processing order and tie-breaking rules of Dijkstra's algorithm and the Bellman-Ford algorithm need not agree, so either tree can result while all shortest-path distances agree. If every reachable vertex has a unique shortest path from $s$, then both correct algorithms must select those same paths.