Shortest Paths & Union-Find

BFS finds shortest paths when every edge counts the same. But roads have distances and networks have latencies - edges carry weights. For weighted shortest paths you need Dijkstra's algorithm. And for a different class of connectivity problems - "are these two nodes in the same group?" - there's a beautifully simple structure called union-find. Together they close out the graph toolkit.

Dijkstra: shortest paths with weights

Dijkstra's algorithm finds the shortest path from a start node to all others in a graph with non-negative edge weights. It's BFS upgraded with a priority queue: instead of exploring by number of edges, always expand the closest-so-far node by total weight:

// Dijkstra: shortest distance from start to every node — O(E log V)
int[] dijkstra(int start, int n, Map<Integer, List<int[]>> graph) {  // neighbor = {to, weight}
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // {node, distance}
    pq.offer(new int[]{start, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int node = cur[0], d = cur[1];
        if (d > dist[node]) continue;                      // stale entry
        for (int[] edge : graph.getOrDefault(node, List.of())) {
            int next = edge[0], weight = edge[1];
            if (d + weight < dist[next]) {                 // found a shorter route
                dist[next] = d + weight;
                pq.offer(new int[]{next, dist[next]});
            }
        }
    }
    return dist;
}

The min-heap always hands you the nearest unfinalized node, and once a node comes out of the heap its shortest distance is settled. (For graphs with negative weights, Dijkstra breaks - use Bellman-Ford instead.) When all weights are equal, Dijkstra reduces to plain BFS.

Union-Find: connectivity in near-constant time

A completely different tool answers "are a and b connected?" and "merge these two groups" efficiently. Union-Find (a disjoint-set structure) keeps each element pointing toward a representative of its set; two elements are connected iff they share a representative:

class UnionFind {
    int[] parent;
    UnionFind(int n) { parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; }

    int find(int x) {                          // representative of x's set
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }  // path compression
        return x;
    }
    void union(int a, int b) { parent[find(a)] = find(b); }   // merge two sets
    boolean connected(int a, int b) { return find(a) == find(b); }
}

With path compression (and union by rank), find and union run in near-constant amortized time. It's the go-to for counting connected components, cycle detection in an undirected graph, and problems like "number of provinces" or Kruskal's minimum spanning tree.