roadmap/Advanced Graphs

Topic 16 / 16

Advanced Graphs

HardNon-Linear~5 days
progress0 / 10 solved

Dijkstra, Bellman-Ford, Prim's, Kruskal's. Weighted shortest paths and minimum spanning trees.

Concept

Advanced graph algorithms handle weighted edges. Dijkstra finds the shortest path in O((V + E) log V) using a min-heap — but only works with non-negative weights. Bellman-Ford handles negative weights in O(V × E) and detects negative cycles. Prim's and Kruskal's build minimum spanning trees. These appear in FAANG system design and hard LC problems.

When to use this pattern
  • ◆Shortest path in a weighted graph → Dijkstra (non-negative weights)
  • ◆Shortest path with negative weights → Bellman-Ford
  • ◆Minimum cost to connect all nodes → Prim's or Kruskal's (MST)
  • ◆Cheapest flights, network delay, city routing problems
  • ◆Floyd-Warshall for all-pairs shortest path
Common patterns
Dijkstra
Min-heap of (cost, node). Relax neighbors. Skip if already visited with lower cost.
Bellman-Ford
Relax all edges V-1 times. Run once more to detect negative cycles.
Kruskal's MST
Sort edges by weight. Use Union-Find to add edge if it doesn't form a cycle.
Prim's MST
Min-heap of (weight, node). Always expand cheapest unvisited neighbor.
Floyd-Warshall
3-nested loops, O(V³). dp[i][j] = min cost from i to j through any intermediate.
Brute force → optimal thinking
Brute force
Try all paths with DFS, track running cost → exponential time.
Observation
If we always expand the currently cheapest known node, we never need to revisit it (Dijkstra's greedy insight).
Optimization
Use a min-heap keyed by distance. When we pop a node, its distance is finalized. Relax all neighbors and push updated distances.
Final complexity
Dijkstra: O((V + E) log V) with binary heap. Bellman-Ford: O(V × E). Kruskal's: O(E log E). Prim's: O(E log V).
Quick Recall Check

What data structure does Dijkstra's algorithm use to always process the nearest node?

When should you use Bellman-Ford instead of Dijkstra?

In Kruskal's MST algorithm, what prevents adding an edge that creates a cycle?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Tries
Progress is saved on this device