What topics does this roadmap cover?

Graph Fundamentals, Depth First Search (DFS), Breadth First Search (BFS), Flood Fill & Grid Graphs, Bipartite Graphs, Tree Fundamentals, Tree Diameter & Center, Subtree DP, Floyd-Warshall Algorithm, Dijkstra's Algorithm, Bellman-Ford Algorithm, Mixed Practice - Shortest Paths, Disjoint Set Union (DSU), Minimum Spanning Trees, Topological Sort, DP on DAGs, Mixed Practice: Graph Traversals, Strongly Connected Components, 2-SAT, Mixed Practice: Connectivity & MST, Rerooting Technique, Euler Tour Technique, Mixed Practice: Tree Fundamentals, Binary Lifting, Lowest Common Ancestor (LCA), Games on Graphs, Heavy-Light Decomposition, Centroid Decomposition, Small-to-Large Merging, Functional Graphs, Mixed Practice: Advanced Tree Techniques, Bridges and Articulation Points, Network Flow, Maximum Bipartite Matching, Minimum Cut, Euler Paths and Circuits, Mixed Practice: Advanced Graphs

How many units are in this roadmap?

This roadmap contains 1633 units across 37 sections.

Is this roadmap free?

Yes, this roadmap is completely free.

Graph Theory - Roadmaps

Dijkstra's Algorithm

Priority queue implementation, lazy deletion, proof of correctness, and optimizations.

Intro

Why BFS is not enough for weighted graphs

Introducing Weights

Edge weights and their meanings

The Greedy Strategy

Dijkstra's key insight

Dijkstra's Algorithm - Setup

Initialization and data structures

Dijkstra's Algorithm - The Loop

Processing nodes in order

The Relaxation Step

Updating distances through edges

Quiz: Dijkstra's Greedy Choice

Knowledge check

Relaxation in Code

Complete code walkthrough

Dijkstra - Implementation

Full pseudocode

Complexity of Dijkstra

Time and space analysis

Path Reconstruction in Dijkstra

Tracking the actual path

Handling Large Weights

Overflow and precision concerns

Quiz: Why Negative Edges Break Dijkstra

Knowledge check

LeetCode 743 Network Delay Time - Problem Statement

Find minimum time for signal propagation

LeetCode 743 Network Delay Time - Intuition

Understanding the problem

LeetCode 743 Network Delay Time - Implementation

Code solution

CSES 1671 Shortest Routes I - Problem Statement

Path reconstruction challenge

LeetCode 1514 Path with Maximum Probability - Problem Statement

Adapting Dijkstra for products

LeetCode 1514 Path with Maximum Probability - Modifying Dijkstra

Different metrics and objectives

Quiz: Dijkstra Modifications

Knowledge check

LeetCode 787 Cheapest Flights Within K Stops - Problem Statement

Dijkstra with constraints

LeetCode 787 Cheapest Flights Within K Stops - State Definition

Expanded state space

LeetCode 787 Cheapest Flights Within K Stops - Algorithm

Modified Dijkstra approach

LeetCode 787 Cheapest Flights Within K Stops - Visited Set

Revisiting nodes in expanded state

LeetCode 787 Cheapest Flights Within K Stops - Implementation

Code solution

LeetCode 787 Cheapest Flights Within K Stops - Lessons

Key takeaways

Quiz: Dijkstra with Constraints

Knowledge check

LeetCode 1631 Path with Minimum Effort - Problem Statement

Minimax path problem

LeetCode 1631 Path with Minimum Effort - Minimax Path

Maximum edge on path

LeetCode 1631 Path with Minimum Effort - Algorithm

Modified Dijkstra for minimax

LeetCode 1631 Path with Minimum Effort - Priority Queue

Heap structure for grid

LeetCode 1631 Path with Minimum Effort - Implementation

Code solution

LeetCode 1631 Path with Minimum Effort - Lessons

When to use minimax Dijkstra

Quiz: Dijkstra on Grids

Knowledge check

CSES 1195 Flight Discount - Problem Statement

One-time discount optimization

CSES 1195 Flight Discount - State Definition

Tracking discount usage

CSES 1195 Flight Discount - Algorithm

Two-state Dijkstra

CSES 1195 Flight Discount - Implementation

Code solution

CSES 1195 Flight Discount - Lessons

State expansion patterns

Section Recap

Summary

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████