This unit covers the all pairs shortest path Floyd-Warshall algorithm, along with the following applications:
- Transitive closure
- Graph minimax / maximin
- Graph safest path / most dangerous path
- Detecting negative weight cycles
Complementary notes can be found in section 4.5 of the book Competitive Programming 3.
- Unit 1: Complexity
- Unit 6: Graph representation
- Unit 14: Graph traversal (mainly BFS)
- Unit 17: Single source Shortest path
- UVa 567 - Route Finding (begin with that one)
- UVa 869 - Airline Comparison
- UVa 1247 - Interstar Transport (you need to print the path)
- Codeforces 295B - Greg and Graph
- UVa 104 - Arbitrage (interesting variant)
- UVa 12179 - Randomly-priced Tickets (not a pure Floyd problem)