Shortest Paths and Topological Sorting

A navigation app does not choose the route with the fewest turns. It chooses the route that takes the least time, and some roads are slower than others. That is a weighted shortest-path problem: the edges have costs, and you want the path with the smallest total cost.

A different kind of question appears when you plan a course schedule or a build: "Data Structures needs Programming first; Algorithms needs Data Structures." Here you do not want a route. You want an order that respects every dependency. That is topological sorting.

Both are classic graph problems and both are common in interviews. They look different, but they share the same toolkit: the adjacency list, a queue-like structure, and careful bookkeeping.

• When BFS is enough, and what to use when it is not.
• How Dijkstra's algorithm works, step by step, and why it needs non-negative weights.
• What Bellman-Ford does differently, and when to mention it.
• What a topological order is, and how to compute one with Kahn's algorithm or DFS.
• How to detect when no valid order exists.
• How to write the complexity in terms of V and E.

BFS finds the path with the fewest edges. If every edge has the same cost (or the graph is unweighted), the path with the fewest edges is the cheapest, and BFS is the right, simplest tool.

Once edges have different costs, fewest edges is no longer cheapest. Consider going from A to C: a direct road of length 10, or two short roads of length 2 each (through B). BFS says "the direct road is one edge, that is shortest", and the real answer is the 4-unit route through B.

A special case is worth knowing by name: if every weight is 0 or 1, a variation called 0-1 BFS (using a double-ended queue) solves it in O(V + E). For general non-negative weights, use Dijkstra.

For a weighted adjacency list, store each edge as a small array {neighbour, weight}:

List<List<int[]>> adj = new ArrayList<>();   // adj.get(u) holds {v, weight} pairs

Sums of weights can grow beyond an int, so distances are stored as long.

Idea. Keep, for every vertex, the best distance found so far from the source (dist), initially infinity except for the source, which is 0. Repeat:

1. Among the vertices not yet settled, pick the one with the smallest dist.
2. Settle it: its distance is now final.
3. Relax each of its outgoing edges u -> v with weight w: if dist[u] + w < dist[v], we have found a shorter way to v, so update dist[v].

The first step needs a fast "give me the smallest" operation, which is exactly a min-heap. Java's PriorityQueue has no "decrease a key" operation, so the standard technique is to simply push a new entry whenever dist[v] improves. The heap may then contain several entries for one vertex. When we pop an entry for a vertex that is already settled, it is stale, so we skip it.

Suppose u has the smallest tentative distance among all unsettled vertices, say d. Could there be a shorter path to u? Any such path would have to leave the settled set through some edge to an unsettled vertex x, and x already has a distance of at least d (because u is the smallest). Then going on from x to u can only add non-negative weight, so the path is at least d. So d is final. This argument uses the non-negativity of the weights in its last step.

With a negative edge, it breaks. Imagine a vertex B that is settled at distance 2. Later, a route through another vertex reaches B with total cost 3 + (-2) = 1. But B was already settled and its outgoing edges were already relaxed with the old distance, so everything downstream of B is now stale. Dijkstra does not go back.

Consider the directed graph with edges 0 -> 1 (4), 0 -> 2 (1), 2 -> 1 (2), 1 -> 3 (1), 2 -> 3 (5), 3 -> 4 (3), plus a vertex 5 with no connections. The shortest distance from 0 to 4 is 1 + 2 + 1 + 3 = 7, going 0 -> 2 -> 1 -> 3 -> 4.

The priority queue holds (vertex, distance) entries, smallest distance first:

Final distances from 0: [0, 3, 1, 4, 7, unreachable].

To recover the path, store a parent for each vertex: whenever dist[v] improves via u, set parent[v] = u. Walk back from the target.

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;import java.util.PriorityQueue;public class Main {    static final long INF = Long.MAX_VALUE;    static List<List<int[]>> buildGraph(int n, int[][] edges) {       // each edge: {from, to, weight}        List<List<int[]>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] e : edges) {            adj.get(e[0]).add(new int[] {e[1], e[2]});        }        return adj;    }    // Requires every weight to be non-negative.    static long[] dijkstra(List<List<int[]>> adj, int source, int[] parent) {        int n = adj.size();        long[] dist = new long[n];        Arrays.fill(dist, INF);        Arrays.fill(parent, -1);        boolean[] settled = new boolean[n];        dist[source] = 0;        PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));   // {vertex, distance}        heap.offer(new long[] {source, 0});        while (!heap.isEmpty()) {            long[] top = heap.poll();            int u = (int) top[0];            if (settled[u]) {                continue;                                  // a stale entry: u was already finalised            }            settled[u] = true;            for (int[] edge : adj.get(u)) {                int v = edge[0];                long candidate = dist[u] + edge[1];        // dist[u] is finite here, so no overflow                if (candidate < dist[v]) {                    dist[v] = candidate;                    parent[v] = u;                    heap.offer(new long[] {v, candidate});                }            }        }        return dist;    }    // Handles negative weights (but not negative cycles). O(V * E).    static long[] bellmanFord(int n, int[][] edges, int source) {        long[] dist = new long[n];        Arrays.fill(dist, INF);        dist[source] = 0;        for (int round = 1; round < n; round++) {            boolean changed = false;            for (int[] e : edges) {                if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) {                    dist[e[1]] = dist[e[0]] + e[2];                    changed = true;                }            }            if (!changed) {                break;                                     // nothing improved: we are done early            }        }        return dist;    }    static List<Integer> pathTo(int target, int[] parent, long[] dist) {        List<Integer> path = new ArrayList<>();        if (dist[target] == INF) {            return path;        }        for (int v = target; v != -1; v = parent[v]) {            path.add(v);        }        Collections.reverse(path);        return path;    }    static String show(long[] dist) {        StringBuilder sb = new StringBuilder("[");        for (int i = 0; i < dist.length; i++) {            sb.append(i == 0 ? "" : ", ").append(dist[i] == INF ? "INF" : String.valueOf(dist[i]));        }        return sb.append("]").toString();    }    public static void main(String[] args) {        int[][] edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {3, 4, 3}};        List<List<int[]>> adj = buildGraph(6, edges);        int[] parent = new int[6];        long[] dist = dijkstra(adj, 0, parent);        System.out.println(show(dist));        System.out.println("path to 4: " + pathTo(4, parent, dist) + ", path to 5: " + pathTo(5, parent, dist));        // A graph with a negative edge: 0->1 (2), 0->2 (3), 2->1 (-2), 1->3 (1). The true distance to 3 is 2.        int[][] negative = {{0, 1, 2}, {0, 2, 3}, {2, 1, -2}, {1, 3, 1}};        long[] viaDijkstra = dijkstra(buildGraph(4, negative), 0, new int[4]);        long[] viaBellmanFord = bellmanFord(4, negative, 0);        System.out.println("negative edge: dijkstra " + show(viaDijkstra) + ", bellman-ford " + show(viaBellmanFord));    }}

[0, 3, 1, 4, 7, INF]path to 4: [0, 2, 1, 3, 4], path to 5: []negative edge: dijkstra [0, 1, 3, 3], bellman-ford [0, 1, 3, 2]

The second experiment shows the limitation. Dijkstra settles vertex 1 at distance 2 (through the direct edge), then later finds the cheaper route 0 -> 2 -> 1 costing 1. It does update dist[1], but it has already relaxed vertex 1's edges using the old value, so the distance to vertex 3 is stuck at 3 instead of the correct 2. Bellman-Ford, which does not make "settled forever" claims, gets it right.

Each edge can cause at most one push into the heap, so the heap holds at most E entries, and each push or pop costs O(log E), which is O(log V) because E is at most V^2. The total is O((V + E) log V) time with a binary heap, and O(V + E) space for the graph, plus O(E) for the heap in the worst case. For a dense graph where E is about V^2, that becomes O(V^2 log V).

Bellman-Ford does not pick favourites. It simply relaxes every edge, over and over. A shortest path has at most V - 1 edges, so after V - 1 rounds of relaxing all edges, every distance is final (even with negative edges). The cost is O(V × E), which is slower than Dijkstra, so use it only when negative edges are possible.

It can also detect a negative cycle (a loop whose total weight is negative, so you could lower the cost forever): if another round still improves a distance, such a cycle is reachable. In that case "shortest path" is not well defined. You can stop early, as the code above does, when a round changes nothing.

Now the second problem. A topological order of a directed acyclic graph (DAG) is a list of all its vertices such that for every edge u -> v, u appears before v. If an edge means "u must come before v" (a prerequisite, a build dependency, a task order), a topological order is a valid schedule.

Two facts:

• A topological order exists if and only if the graph has no directed cycle. If A needs B and B needs A, nothing can go first.
• There is usually more than one valid order. A single graph with several independent tasks has many.

The first vertex in any valid order must have no incoming edges: nothing has to come before it. So:

1. Compute the in-degree (number of incoming edges) of every vertex.
2. Put all vertices with in-degree 0 in a queue.
3. Repeatedly remove a vertex u from the queue and append it to the order. Then, for every edge u -> v, remove that edge by decreasing v's in-degree. If v's in-degree becomes 0, v is now free to go, so enqueue it.
4. At the end, if the order contains all V vertices, we are done. If fewer, some vertices never reached in-degree 0: they are stuck behind a cycle, and no valid order exists.

That last step is a free cycle detector.

A second method uses DFS. When DFS finishes a vertex (after exploring all vertices reachable from it), every vertex that must come after it has already been finished. So record vertices in finishing order and reverse the list. You still need the three-state cycle check from the graphs article, because DFS on a cyclic graph would otherwise give a meaningless order.

There are four courses. Course 1 needs 0. Course 2 needs 0. Course 3 needs both 1 and 2. As directed edges ("before"): 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3.

Dry run of Kahn's algorithm. In-degrees: 0:0, 1:1, 2:1, 3:2.

All four vertices were placed, so the order 0, 1, 2, 3 is valid. The DFS method gives a different valid order (0, 2, 1, 3) because it explores in a different sequence.

If the graph were 0 -> 1, 1 -> 0, both vertices start with in-degree 1, the queue is empty from the beginning, and the order has 0 of 2 vertices. That is the signal for "impossible".

// File: Main.javaimport java.util.ArrayDeque;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Queue;public class Main {    static List<List<Integer>> buildGraph(int n, int[][] edges) {        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] e : edges) {            adj.get(e[0]).add(e[1]);          // e[0] must come before e[1]        }        return adj;    }    // Kahn's algorithm. Returns null if the graph has a cycle.    static List<Integer> topologicalOrder(int n, int[][] edges) {        List<List<Integer>> adj = buildGraph(n, edges);        int[] indegree = new int[n];        for (int[] e : edges) {            indegree[e[1]]++;        }        Queue<Integer> queue = new ArrayDeque<>();        for (int v = 0; v < n; v++) {            if (indegree[v] == 0) {                queue.offer(v);            }        }        List<Integer> order = new ArrayList<>();        while (!queue.isEmpty()) {            int u = queue.poll();            order.add(u);            for (int v : adj.get(u)) {                indegree[v]--;                  // remove the edge u -> v                if (indegree[v] == 0) {                    queue.offer(v);                }            }        }        return order.size() == n ? order : null;    }    // DFS version: reverse of the finishing order. Returns null if there is a cycle.    static List<Integer> topologicalOrderDfs(int n, int[][] edges) {        List<List<Integer>> adj = buildGraph(n, edges);        int[] state = new int[n];               // 0 unvisited, 1 on the current path, 2 finished        List<Integer> finished = new ArrayList<>();        for (int v = 0; v < n; v++) {            if (state[v] == 0 && !visit(adj, v, state, finished)) {                return null;            }        }        Collections.reverse(finished);        return finished;    }    private static boolean visit(List<List<Integer>> adj, int u, int[] state, List<Integer> finished) {        state[u] = 1;        for (int v : adj.get(u)) {            if (state[v] == 1) {                return false;                   // back edge: a cycle            }            if (state[v] == 0 && !visit(adj, v, state, finished)) {                return false;            }        }        state[u] = 2;        finished.add(u);                        // u finishes after everything that must come after it        return true;    }    static String show(List<Integer> order) {        return order == null ? "cycle, no valid order" : order.toString();    }    public static void main(String[] args) {        int[][] courses = {{0, 1}, {0, 2}, {1, 3}, {2, 3}};        System.out.println(show(topologicalOrder(4, courses)) + " / " + show(topologicalOrderDfs(4, courses)));        int[][] cyclic = {{0, 1}, {1, 0}};        System.out.println(show(topologicalOrder(2, cyclic)) + " / " + show(topologicalOrderDfs(2, cyclic)));        System.out.println(show(topologicalOrder(3, new int[][] {})));        System.out.println(show(topologicalOrder(0, new int[][] {})));        int[][] partial = {{0, 1}, {1, 2}, {2, 1}, {0, 3}};        System.out.println(show(topologicalOrder(4, partial)));    }}

[0, 1, 2, 3] / [0, 2, 1, 3]cycle, no valid order / cycle, no valid order[0, 1, 2][]cycle, no valid order

The last test has a cycle 1 <-> 2 reachable from 0. Kahn's algorithm can still place 0 and 3 (they have no cyclic dependency), but it can never place 1 or 2. The order has only 2 of 4 vertices, so the method reports a cycle. A valid answer to "can I finish all the courses?" is exactly "did the order contain every vertex?".

Computing in-degrees touches each edge once, the queue handles each vertex once, and each edge is "removed" once. So Kahn's algorithm is O(V + E) time and O(V + E) space. The DFS version has the same cost.

If the graph is a DAG, you can find shortest paths from a source in O(V + E) even with negative weights: process the vertices in topological order, and relax each vertex's outgoing edges once. Because every edge points forward in the order, a vertex's distance is final by the time we process it. It is a nice example of a sort making a hard problem easy.

• Using BFS on a weighted graph. It returns the fewest edges, not the least cost.
• Using Dijkstra with negative weights. It can give wrong answers silently.
• Overflow with "infinity". If you store Integer.MAX_VALUE as infinity and add a weight to it, the sum wraps around to a negative number and appears to be an improvement. Use long and skip relaxing from unreachable vertices.
• Forgetting stale heap entries. Skip a popped vertex if it is already settled (or if the popped distance is larger than dist[u]).
• A comparator written as a subtraction for distances. Use Long.compare.
• Unreachable vertices. Their distance stays at infinity. Report it clearly (-1 or "unreachable").
• Zero-weight edges are fine for Dijkstra. Negative ones are not.
• Topological order that is "the" answer. Many orders may be valid. If the problem needs a specific one (such as the lexicographically smallest), use a priority queue instead of a queue in Kahn's algorithm.
• Not checking for a cycle. If the order has fewer than V vertices, there is no valid order.
• Edge direction mix-ups. "Course a requires course b" is the edge b -> a. Draw one example to be sure.
• Parallel edges and self-loops. A self-loop is a cycle in the dependency sense. Parallel edges are harmless in Dijkstra, but in Kahn's algorithm they each count towards the in-degree.

static int[] bellmanFordBuggy(int n, int[][] edges, int source) {    int[] dist = new int[n];    Arrays.fill(dist, Integer.MAX_VALUE);    dist[source] = 0;    for (int round = 1; round < n; round++) {        for (int[] e : edges) {            if (dist[e[0]] + e[2] < dist[e[1]]) {                dist[e[1]] = dist[e[0]] + e[2];            }        }    }    return dist;}

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.PriorityQueue;public class Main {    public static void main(String[] args) {        int n = 6;        int[][] edges = {{0, 1, 7}, {0, 2, 9}, {0, 5, 14}, {1, 2, 10}, {1, 3, 15}, {2, 3, 11}, {2, 5, 2}, {3, 4, 6}, {5, 4, 9}};        List<List<int[]>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] e : edges) {            adj.get(e[0]).add(new int[] {e[1], e[2]});        }        long[] dist = new long[n];        Arrays.fill(dist, Long.MAX_VALUE);        dist[0] = 0;        boolean[] settled = new boolean[n];        List<Integer> settleOrder = new ArrayList<>();        PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> a[1] != b[1] ? Long.compare(a[1], b[1]) : Long.compare(a[0], b[0]));        heap.offer(new long[] {0, 0});        while (!heap.isEmpty()) {            long[] top = heap.poll();            int u = (int) top[0];            if (settled[u]) {                continue;            }            settled[u] = true;            settleOrder.add(u);            for (int[] e : adj.get(u)) {                if (dist[u] + e[1] < dist[e[0]]) {                    dist[e[0]] = dist[u] + e[1];                    heap.offer(new long[] {e[0], dist[e[0]]});                }            }        }        System.out.println(settleOrder + " " + Arrays.toString(dist));    }}

[0, 1, 2, 5, 3, 4] [0, 7, 9, 20, 20, 11]

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.PriorityQueue;public class Main {    static int networkDelayTime(int[][] times, int n, int k) {        List<List<int[]>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] t : times) {            adj.get(t[0] - 1).add(new int[] {t[1] - 1, t[2]});        }        long[] dist = new long[n];        Arrays.fill(dist, Long.MAX_VALUE);        dist[k - 1] = 0;        boolean[] settled = new boolean[n];        PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));        heap.offer(new long[] {k - 1, 0});        while (!heap.isEmpty()) {            long[] top = heap.poll();            int u = (int) top[0];            if (settled[u]) {                continue;            }            settled[u] = true;            for (int[] e : adj.get(u)) {                if (dist[u] + e[1] < dist[e[0]]) {                    dist[e[0]] = dist[u] + e[1];                    heap.offer(new long[] {e[0], dist[e[0]]});                }            }        }        long worst = 0;        for (long d : dist) {            if (d == Long.MAX_VALUE) {                return -1;                              // some node never receives the signal            }            worst = Math.max(worst, d);        }        return (int) worst;    }    public static void main(String[] args) {        System.out.println(networkDelayTime(new int[][] {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));        System.out.println(networkDelayTime(new int[][] {{1, 2, 1}}, 2, 2));        System.out.println(networkDelayTime(new int[][] {{1, 2, 1}}, 2, 1));        System.out.println(networkDelayTime(new int[][] {}, 1, 1));    }}

2-110

// File: Main.javaimport java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;public class Main {    static List<Integer> smallestOrder(int n, int[][] edges) {        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        int[] indegree = new int[n];        for (int[] e : edges) {            adj.get(e[0]).add(e[1]);            indegree[e[1]]++;        }        PriorityQueue<Integer> available = new PriorityQueue<>();        for (int v = 0; v < n; v++) {            if (indegree[v] == 0) {                available.offer(v);            }        }        List<Integer> order = new ArrayList<>();        while (!available.isEmpty()) {            int u = available.poll();                   // the smallest vertex that is free            order.add(u);            for (int v : adj.get(u)) {                if (--indegree[v] == 0) {                    available.offer(v);                }            }        }        return order.size() == n ? order : new ArrayList<>();    }    public static void main(String[] args) {        int[][] edges = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};        System.out.println(smallestOrder(6, edges));        System.out.println(smallestOrder(2, new int[][] {{0, 1}, {1, 0}}));        System.out.println(smallestOrder(3, new int[][] {}));    }}

[4, 5, 0, 2, 3, 1][][0, 1, 2]

// File: Main.javaimport java.util.Arrays;public class Main {    static int[] bellmanFordBuggy(int n, int[][] edges, int source) {        int[] dist = new int[n];        Arrays.fill(dist, Integer.MAX_VALUE);        dist[source] = 0;        for (int round = 1; round < n; round++) {            for (int[] e : edges) {                if (dist[e[0]] + e[2] < dist[e[1]]) {                    dist[e[1]] = dist[e[0]] + e[2];                }            }        }        return dist;    }    static int[] bellmanFordFixed(int n, int[][] edges, int source) {        int[] dist = new int[n];        Arrays.fill(dist, Integer.MAX_VALUE);        dist[source] = 0;        for (int round = 1; round < n; round++) {            for (int[] e : edges) {                if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {                    dist[e[1]] = dist[e[0]] + e[2];                }            }        }        return dist;    }    public static void main(String[] args) {        int[][] edges = {{0, 1, 5}, {2, 3, 1}};        System.out.println(Arrays.toString(bellmanFordBuggy(4, edges, 0)));        System.out.println(Arrays.toString(bellmanFordFixed(4, edges, 0)));    }}

[0, 5, 2147483647, -2147483648][0, 5, 2147483647, 2147483647]

// File: Main.javaimport java.util.ArrayDeque;import java.util.LinkedHashMap;import java.util.LinkedHashSet;import java.util.Map;import java.util.Queue;import java.util.Set;public class Main {    static String alienOrder(String[] words) {        Map<Character, Set<Character>> adj = new LinkedHashMap<>();        Map<Character, Integer> indegree = new LinkedHashMap<>();        for (String word : words) {            for (char c : word.toCharArray()) {                adj.putIfAbsent(c, new LinkedHashSet<>());                indegree.putIfAbsent(c, 0);            }        }        for (int i = 0; i + 1 < words.length; i++) {            String a = words[i];            String b = words[i + 1];            if (a.length() > b.length() && a.startsWith(b)) {                return "";                                     // a word cannot come before its own prefix            }            for (int j = 0; j < Math.min(a.length(), b.length()); j++) {                char x = a.charAt(j);                char y = b.charAt(j);                if (x != y) {                    if (adj.get(x).add(y)) {                   // count each distinct edge once                        indegree.merge(y, 1, Integer::sum);                    }                    break;                                     // only the first difference tells us anything                }            }        }        Queue<Character> queue = new ArrayDeque<>();        for (Map.Entry<Character, Integer> entry : indegree.entrySet()) {            if (entry.getValue() == 0) {                queue.offer(entry.getKey());            }        }        StringBuilder order = new StringBuilder();        while (!queue.isEmpty()) {            char c = queue.poll();            order.append(c);            for (char next : adj.get(c)) {                if (indegree.merge(next, -1, Integer::sum) == 0) {                    queue.offer(next);                }            }        }        return order.length() == indegree.size() ? order.toString() : "";    }    public static void main(String[] args) {        System.out.println("[" + alienOrder(new String[] {"wrt", "wrf", "er", "ett", "rftt"}) + "]");        System.out.println("[" + alienOrder(new String[] {"z", "x"}) + "]");        System.out.println("[" + alienOrder(new String[] {"z", "x", "z"}) + "]");        System.out.println("[" + alienOrder(new String[] {"abc", "ab"}) + "]");        System.out.println("[" + alienOrder(new String[] {"a"}) + "]");        System.out.println("[" + alienOrder(new String[] {}) + "]");    }}

[wertf][zx][][][a][]

• Next: Dynamic Programming: Learn to Recognize Overlapping Subproblems leaves graphs and shows how to avoid repeating work in a different way.
• Related: Range Queries and Disjoint Set Union uses union-find for Kruskal's minimum spanning tree, a cousin of the problems here. The study plan in Your 12-Week DSA Study and Revision Plan shows where to schedule graph practice.
• Practice habit: before choosing an algorithm for a graph problem, write down three facts: directed or undirected, weighted or not, and whether weights can be negative. Those three decide almost everything.