Proofs of the shortest paths tree p

Proofs of the shortest paths tree property for the general relaxation-based algorithm remained not straightforward fordecades. For example, in both editions of the popular textbook [5], this proof is about two and a half pages long. Muchshorter proofs appear in [18,13]. However, they are indirect: for a graph with no negative cycle, the key lemma proves thatback-pointers π computed by the algorithm never form a cycle, and this lemma implies the property. In contrast, the proofof the shortest paths tree property for the Dijkstra algorithm is straightforward: when the final, true distance is set for avertex, also a new leaf edge to it is added to the current shortest paths tree. We suggest a similar proof for an arbitraryrelaxation-based algorithm processing an arbitrary graph.