Advanced Graph Algorithms

Dijkstra's Algorithm

Finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights.

Use a Min-Heap (Priority Queue)

Always greedily expand the node with the current shortest known distance. In Python, use heapq with tuples (distance, node).

Distance Array

Maintain a dist array initialized to infinity. Update it when a shorter path is found.

Time Complexity: O((V + E) log V)

Disjoint Set Union (DSU / Union-Find)

A data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

Find with Path Compression

Make every visited node point directly to the root. Amortizes time complexity to near O(1).

Union by Rank / Size

Always attach the smaller tree under the root of the larger tree to keep the tree shallow.

Time Complexity: O(α(V)) per operation (essentially O(1)).

Dijkstra's Algorithm (Shortest Path)

import heapq

def dijkstra(graph, start):
    # graph is an adjacency list: {node: [(weight, neighbor), ...]}
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]  # (distance, node)
    
    while pq:
        curr_dist, u = heapq.heappop(pq)
        
        # Optimization: Skip if we found a shorter path already
        if curr_dist > dist[u]:
            continue
            
        for weight, v in graph[u]:
            new_dist = curr_dist + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    return dist

Disjoint Set Union (DSU)

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n
        
    def find(self, i):
        if self.parent[i] == i:
            return i
        # Path compression
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
        
    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        
        if root_i != root_j:
            # Union by rank
            if self.rank[root_i] < self.rank[root_j]:
                root_i, root_j = root_j, root_i
            self.parent[root_j] = root_i
            if self.rank[root_i] == self.rank[root_j]:
                self.rank[root_i] += 1
            return True  # Successfully merged
        return False  # Already in same set (Cycle detected)

LeetCode Problems

MediumNetwork Delay TimeStandard Dijkstra
MediumPath With Minimum EffortDijkstra with max-edge logic
MediumRedundant ConnectionDSU for cycle detection
MediumNumber of Operations to Make Network ConnectedDSU connected components
MediumAccounts MergeDSU on strings/emails
HardSwim in Rising WaterDijkstra on Grid / Kruskal