Level 4. Graphs and Dynamic Programming

Graph traversals, shortest paths, spanning trees, and your first dynamic programming problems.

The two pillars of the middle level: graphs (DFS, BFS, Dijkstra, spanning trees) and dynamic programming. "Real" contest algorithmics starts at this level — as do most problems of city and national rounds. The readiness criterion for level 5: you translate a word problem into a graph on your own and solve simple DPs (the staircase, subarrays), explaining what a state and a transition are.

In this section

  1. 1
    Graphs: Representation, BFS and DFS

    Graphs: the adjacency list, depth- and breadth-first search, connected components and shortest paths.

  2. 2
    Shortest Paths: Dijkstra and Floyd

    Shortest paths in a weighted graph: Dijkstra with a heap in O(m log n) and Floyd in O(n³).

  3. 3
    Minimum Spanning Tree

    The minimum spanning tree: Kruskal's algorithm = sorting edges + DSU.

  4. 4
    Dynamic Programming: Basics

    Dynamic programming: states, transitions, the base case — the staircase and the maximum subarray.

Доска