Advanced Graphs

Weighted shortest paths and connectivity beyond plain BFS/DFS — Dijkstra, Union-Find, and minimum spanning trees.

Study first: Graphs

What it is

Once edges carry weights, "shortest path" stops being "fewest edges" (BFS) and becomes "least total weight" — which needs different algorithms.

Core algorithms

Dijkstra's algorithm — repeatedly pop the closest unvisited node from a min-heap and relax its neighbors' distances; O((V + E) log V). Requires non-negative weights.
Bellman-Ford — relaxes every edge V−1 times; slower (O(VE)) but handles negative weights and detects negative cycles.
Union-Find (Disjoint Set Union) — tracks which nodes are already connected in near-O(1) per operation (with path compression + union by rank); the standard tool for Kruskal's minimum spanning tree and cycle detection in undirected graphs.

Why Dijkstra needs a heap

Without a priority queue, finding "the closest unvisited node" is an O(V) scan every time, giving O(V²) total. A min-heap turns that lookup into O(log V), which is why Heaps is a prerequisite here.