Week #08 | |

Pedro Ribeiro - DCC/FCUP |

*Shortest Distances*:- I understand the
**Dijkstra algorithm**, its complexity, how to implement it, and how I can adapt it to different situations - I understand the
**Bellman-Ford algorithm**, its complexity, how to implement it, and how I can adapt it to different situations - I understand the
**Floyd-Warshall algorithm**, how to implement it, and how I can adapt it to different situations

- I understand the
*Minimum Spanning Trees*:- I understand the concept of a
**minimum spanning tree** - I understand the
**Prim Algorithm**, its complexity and how to implement it efficiently with a priority queue. - I understand the
**Kruskal Algorithm**, its complexity and how to implement it efficiently with a disjoint-set data structure.

- I understand the concept of a
*Maximum Flows*:- I understand the concept of a
**maximum flow**, and how some problems can reduce to it - I understand the
**Ford-Fulkerson method**, its complexity and its implementation using the**Edmonds-Karp algorithm**. - I know that mode efficient solutions exist, such as the
**Hopcroft–Karp algorithm**for maximum bipartite matching and what can be seen as its generalization,**Dinic's algorithm**.

- I understand the concept of a

**Shortest Distances**- Chapter 13 of Competitive Programmer's Handbook book
- Section 4.4 and 4.5 of the Competitive Programming book
**Visualizations:**Single Source Shortest Paths (VisuAlgo), Dijkstra, Floyd-Warshall (Data Structure Visualizations)**Implementations: Dijkstra, Bellman-Ford, Floyd-Warshall (E-Maxx Algorithms in English)****Minimum Spanning Trees**- Chapter 15 of Competitive Programmer's Handbook book
- Section 4.3 and 2.3.2 of the Competitive Programming book
**Visualizations:**Minimum Spanning Tree, Union-Find Disjoint Sets (VisuAlgo), Prim, Kruskal, Disjoint Sets (Data Structure Visualizations)**Implementations: Prim, Kruskal / with disjoint-set (E-Maxx Algorithms in English)****Maximum Flows**- Chapter 20 of Competitive Programmer's Handbook book
- Section 4.6 of the Competitive Programming book
**Visualizations:**Max Flow / Min Cut (VisuAlgo)**Implementations: Edmonds-Karp, Dinic (E-Maxx Algorithms in English)**

Pedro Ribeiro - DCC/FCUP |
**Último update:**