Module 7.2 ⏱ 45 min read ⚡ Shortest Paths & MSTs

Shortest Path & Minimum Spanning Trees

Master Dijkstra's algorithm for shortest paths, Disjoint Set Union (DSU / Union-Find) data structures, and Kruskal's Minimum Spanning Tree algorithm.

1. Dijkstra's Algorithm & Shortest Path Paradigms

Dijkstra's Algorithm is a greedy algorithm used to solve the single-source shortest path problem for a graph with non-negative edge weights. It iteratively selects the unvisited vertex with the smallest known tentative distance, relaxes its outgoing neighbor connections, and tracks shortest pathways using a Min-Priority Queue.

Complexity: Using an adjacency list paired with a binary heap or priority queue, Dijkstra's algorithm runs in $O((V + E) \log V)$ time, making it highly efficient for sparse network topologies.

2. Disjoint Set Union (DSU) & Kruskal's Algorithm

Disjoint Set Union (DSU / Union-Find): A data structure that tracks a partition of a set into disjoint subsets. It supports two primary operations: `find` (to locate the representative root of an element's set) and `union` (to merge two sets). Through optimization heuristics like **path compression** and **union by rank/size**, amortized time complexity drops to nearly constant time, $O(\alpha(n))$.

Kruskal's Algorithm: A classic approach for finding a Minimum Spanning Tree (MST) in a connected weighted graph. It sorts all edges in ascending order of weight and greedily adds them to the forest using a DSU data structure to prevent cycles until all vertices are connected.

// C++ Solution: Network Delay Time (Dijkstra's Algorithm)
#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>

class Solution {
public:
    int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) {
        std::unordered_map<int, std::vector<std::pair<int, int>>> adj;
        for (const auto& t : times) {
            adj[t[0]].push_back({t[1], t[2]});
        }
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
        std::vector<int> dist(n + 1, INT_MAX);
        
        dist[k] = 0;
        pq.push({0, k});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            if (adj.count(u)) {
                for (auto& edge : adj[u]) {
                    int v = edge.first;
                    int weight = edge.second;
                    if (dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                        pq.push({dist[v], v});
                    }
                }
            }
        }
        
        int maxDist = 0;
        for (int i = 1; i <= n; ++i) {
            if (dist[i] == INT_MAX) return -1;
            maxDist = std::max(maxDist, dist[i]);
        }
        return maxDist;
    }
};
            

# Python Solution: Network Delay Time (Dijkstra's Algorithm)
import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        adj = defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))
            
        min_heap = [(0, k)]
        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[k] = 0
        
        while min_heap:
            d, u = heapq.heappop(min_heap)
            
            if d > dist[u]:
                continue
                
            for v, weight in adj[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    heapq.heappush(min_heap, (dist[v], v))
                    
        max_dist = max(dist.values())
        return max_dist if max_dist != float('inf') else -1
            

// Java Solution: Network Delay Time (Dijkstra's Algorithm)
import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] t : times) {
            adj.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        dist[k] = 0;
        pq.offer(new int[]{0, k});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];
            
            if (d > dist[u]) continue;
            
            if (adj.containsKey(u)) {
                for (int[] edge : adj.get(u)) {
                    int v = edge[0], weight = edge[1];
                    if (dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                        pq.offer(new int[]{dist[v], v});
                    }
                }
            }
        }
        
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxDist = Math.max(maxDist, dist[i]);
        }
        return maxDist;
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for tracking Network Delay Time using Dijkstra and finding Redundant Connections using DSU.

Quick Check: Test Your Intuition

What is the primary purpose of path compression in a Disjoint Set Union (DSU / Union-Find) data structure?