Advanced Graph Algorithms: Dijkstra, Topological Sort, and Disjoint Set Union (DSU)

Scenario context

Graph algorithms are the backbone of networking, scheduling, and connection analysis. This guide explores Dijkstra's pathfinding, Topological Sorting for dependency resolution, and Disjoint Set Union (DSU) for cycle detection, complete with runnable Java code.

Imagine you are designing the routing engine for a ride-sharing service. You need to calculate the fastest path from a driver's current position to a cu…

This walkthrough focuses on The Network Connectivity Problem: Navigating Relationships.

Before making a design choice, clarify:

• Imagine you are designing the routing engine for a ride-sharing service.
• You need to calculate the fastest path from a driver's current position to a customer.
• The city is modeled as a network of intersections (nodes) connected by roads (edges), where each road carries a travel time cost (edge weight).

Concepts in play: graph-traversal-algorithms, jvm-internals-and-garbage-collection, tree-data-structures, stack-and-queue-data-structures

Stage 1 — Core Intuitions: Graphs, Edges, and Paths

• A graph $G = (V, E)$ consists of a set of vertices $V$ and a set of edges $E$.
• Undirected: Directed edges specify a one-way path ($A \to B$); undirected edges allow bidirectional travel ($A \leftrightarrow B$).
• Unweighted: Weighted edges carry a cost; unweighted edges represent simple connectivity.
• Acyclic: Cyclic graphs contain paths that loop back to starting nodes; acyclic graphs (like trees or DAGs) contain no loops.

Observable outcome: Acyclic: Cyclic graphs contain paths that loop back to starting nodes; acyclic graphs (like trees or DAGs) contain no loops.

Stage 2 — How Graph Algorithms Traverse States: Breadth, Depth, and Priority

• Graph algorithms explore the state space using different container strategies: 1.
• Queue (BFS / Kahn's): Explores neighbors level-by-level.
• This is optimal for unweighted shortest paths and topological ordering.
• Stack / Recursion (DFS): Explores as deep as possible before backtracking.

Observable outcome: Stack / Recursion (DFS): Explores as deep as possible before backtracking.

Stage 3 — Deep Dive: Complexities and Dynamic Data Representations

• Selecting the correct data structures directly dictates the time and space complexity of graph algorithms.
• The Internals of Adjacency Lists and Priority Queues For sparse graphs (where the number of edges $ E $ is much smaller than $ V ^2$), representing the graph as an Adjacency List is highly efficient.
• In Java, this is typically represented as a list of lists: List<List<Edge .
• Dijkstra's algorithm relies on a Priority Queue (Min-Heap) to extract the minimum distance node.

Observable outcome: Dijkstra's algorithm relies on a Priority Queue (Min-Heap) to extract the minimum distance node.

Stage 4 — Visualizing Shortest Path Finding: Dijkstra's Step-by-Step State

• Let us trace Dijkstra's algorithm finding the shortest path from Node 0 to Node 2 in this weighted graph: Edge $0 \to 1$ (weight 4) Edge $0 \to 2$ (weight 9) Edge $1 \to 2$ (weight 3) 📊 Dijkstra Pathfinding Process Let…
• In Step 2, visiting Node 1 allows us to relax the distance to Node 2 from 9 down to 7 (since $4 + 3 < 9$).
• The heap extracts (7, 2) next, successfully finding the shortest path.

flowchart LR
    Node0((Node 0)) -->|Wt: 4| Node1((Node 1))
    Node0 -->|Wt: 9| Node2((Node 2))
    Node1 -->|Wt: 3| Node2
    style Node0 fill:#e8f4e8,stroke:#28a745
    style Node2 fill:#fff3cd,stroke:#ffc107

Observable outcome: The heap extracts (7, 2) next, successfully finding the shortest path.

Stage 5 — Real-World Applications: GPS Navigation, Build Systems, and Network Protocols

• Graph algorithms power many standard applications: Google & Apple Maps: Use Dijkstra variants (like A search with heuristics and contraction hierarchies) to calculate traffic-aware driving routes in milliseconds.
• Build Engines (Webpack, Maven): Webpack parses dependencies between JavaScript files, generating a directed graph.
• It uses Topological Sorting to decide the exact compilation sequence, ensuring libraries compile before the files that import them.
• Network Routing (OSPF): The Open Shortest Path First protocol uses Dijkstra's algorithm to calculate optimal data packet routing tables across global routers.

Observable outcome: Network Routing (OSPF): The Open Shortest Path First protocol uses Dijkstra's algorithm to calculate optimal data packet routing tables across global routers.

Stage 6 — Implementing Graph Patterns: Three Classic Interview Solutions

• Let's implement Dijkstra's shortest path, Kahn's Topological Sort, and DSU Cycle Detection in Java.
• Dijkstra's Shortest Path Problem: Find the shortest path from a source node to all other nodes in a weighted graph.
• Implementation: Using adjacency lists and a Java PriorityQueue .
• Topological Sort (Kahn's BFS-based Algorithm) Problem: Find a linear ordering of vertices such that for every directed edge $u \to v$, vertex $u$ comes before $v$.

import java.util.*;

public class DijkstraSolver {
    public static class Edge {
        int target, weight;
        public Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }

    public static class NodePair implements Comparable<NodePair> {
        int node, distance;
        public NodePair(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }
        @Override
        public int compareTo(NodePair other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

    public int[] findShortestPaths(List<List<Edge>> graph, int source, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<NodePair> minHeap = new PriorityQueue<>();
        minHeap.offer(new NodePair(source, 0));

        while (!minHeap.isEmpty()) {
            NodePair current = minHeap.poll();
            int u = current.node;

            // Skip if we've already found a shorter path to this node
            if (current.distance > dist[u]) continue;

            for (Edge edge : graph.get(u)) {
                int v = edge.target;
                int weight = edge.weight;

                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    minHeap.offer(new NodePair(v, dist[v]));
                }
            }
        }
        return dist;
    }
}

import java.util.*;

public class TopologicalSorter {
    public int[] sort(List<List<Integer>> graph, int n) {
        int[] inDegree = new int[n];
        for (int u = 0; u < n; u++) {
            for (int v : graph.get(u)) {
                inDegree[v]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] order = new int[n];
        int idx = 0;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            order[idx++] = u;

            for (int v : graph.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // If index doesn't reach N, the graph contains a cycle (cannot sort)
        if (idx != n) {
            return new int[0];
        }
        return order;
    }
}

Observable outcome: Topological Sort (Kahn's BFS-based Algorithm) Problem: Find a linear ordering of vertices such that for every directed edge $u \to v$, vertex $u$ comes before $v$.

End-to-end outcome

After working through the stages, you should be able to explain:

• Avoid these standard bugs when coding graph algorithms during interviews: 1.
• Forgetting Visited Check in Dijkstra: In Dijkstra, always check if the current polled distance is larger than the recorded distance ( current.distance dist[u] ).
• Weighted Paths: Use Dijkstra's algorithm with a Min-Heap.
• Dependency Resolution: Use Topological Sorting (Kahn's algorithm) on directed acyclic graphs (DAGs).

Alternatives considered

Decision Guide: DFS vs BFS vs Dijkstra vs DSU

Use this guide to map your graph problem to the correct algorithmic strategy.

Failure and degraded modes

Trade-offs and Failure Modes: Infinite Loops, Stack Overflows, and Negative Cycles

• Detection: When working with graphs, be aware of these failure modes: Negative Cycles (Dijkstra): If a graph contains a negative edge weight cycle (e.g., $A \to B \to A$ with a net negative cost), Dijkstra's al…
• User or operator impact: When working with graphs, be aware of these failure modes: Negative Cycles (Dijkstra): If a graph contains a negative edge weight cycle (e.g., $A \to B \to A$ with a net negative cost), Dijkstra's al…