Main learning outcomes for this class
- 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
- 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
- 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.
Study Material
Main References
- Shortest Distances
- Minimum Spanning Trees
- Maximum Flows
Pedro Ribeiro - DCC/FCUP | Last update:
