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)