Dijkstra and shortest paths · 1 of 4
Shortest paths in weighted graphs
Define the length of a path and the distance in a weighted graph, see what BFS can and cannot do with weights, and find distances by relaxing every edge in rounds.
Books1
Links2
- Shortest Paths with Non-Negative Edge Weights Solves CSES Shortest Routes I with Dijkstra and Shortest Routes II with Floyd-Warshall, and has a graded list of problems to practice on. usaco.guide (opens in a new tab)
- 最短路 (Shortest paths) Floyd, Bellman-Ford with its queue variant SPFA, Dijkstra with a correctness proof, Johnson’s algorithm and a table comparing all of them. oi-wiki.org (opens in a new tab)