Dijkstra trace, classic 6-vertex graph, source A ================================================ pop 0 @0 settled relax 0 -> 1 dist[1] = 7 relax 0 -> 2 dist[2] = 9 relax 0 -> 5 dist[5] = 14 pop 1 @7 settled relax 1 -> 3 dist[3] = 22 pop 2 @9 settled relax 2 -> 3 dist[3] = 20 relax 2 -> 5 dist[5] = 11 pop 5 @11 settled relax 5 -> 4 dist[4] = 20 pop 5 @14 stale (best known is 11) -> skipped pop 4 @20 settled pop 3 @20 settled pop 3 @22 stale (best known is 20) -> skipped dist[A] = 0 dist[B] = 7 dist[C] = 9 dist[D] = 20 dist[E] = 20 dist[F] = 11 cheapest path to E: A -> C -> F -> E (cost 20) stats: Stats[pushes=8, pops=8, stalePops=2, edgeScans=18, relaxations=7]