← Lab · Chapter: Shortest paths

Shortest paths: Dijkstra, Bellman–Ford, acyclic graphs

The labels d(i) and pred(i) step by step: Dijkstra's permanent nodes, Bellman–Ford's passes with negative cycles, the topological order; at the end the tree and the potentials certificate. Choose the algorithm and the source; ◀ ▶ one step at a time, «Run» to watch them all; the «Instance» menu (the chapter's instances), «Random» and «Edit…» change the graph.