A. Prerequisites

Competitive Programming βΈ± Week 06

1. Single-Source Shortest Paths

πŸ“–

If you are interested in learning thee proofs of the algorithms we discuss, you could take a a look at this chapter.

Video Reference - Dijkstra (Introduction)
Video Reference - Dijkstra (Analysis)
Video Reference - Bellman-Ford (Negative cycles)

For SSSP, you can also try out this visualgo module.

2. All-Pairs Shortest Paths

πŸ“–

We describe the algorithm described in Section 9.8 in this chapter. It's readable stand alone, but you could read the whole chapter if you want to experience a natural build-up to the ideas of the final algorithm :)

Video Reference - Floyd-Warshall (APSP)