Advanced Graph Algorithms
Once a graph carries weights or dependencies, plain BFS and DFS stop being enough. Shortest-path, spanning-tree, and ordering algorithms each exploit a different structural guarantee — and knowing which guarantee a graph offers is what selects the algorithm.
Reading the Problem Before Picking the Algorithm
Graph problems rarely announce which algorithm they need, but a small number of properties determine the answer almost entirely. Checking them in order is faster and more reliable than pattern-matching against remembered problems.
Are the edges weighted? If every edge costs the same, shortest paths are a BFS, at O(V + E). Reaching for Dijkstra here is a common and costly mistake — it adds a priority queue and a log factor to solve a problem BFS already solves optimally.
Can weights be negative? Negative edges invalidate Dijkstra's central assumption and require Bellman-Ford. If negative cycles may exist, only Bellman-Ford can detect them, and shortest paths become undefined in their presence.
One source, or all pairs? A single source calls for Dijkstra or Bellman-Ford. All pairs on a dense graph calls for Floyd-Warshall, at O(V³) with a triple loop that is far simpler than running a single-source algorithm V times.
Do you want paths, or a connecting structure? A shortest path connects two vertices as cheaply as possible. A minimum spanning tree connects all vertices with minimum total edge weight, and generally does not contain the shortest path between any particular pair. Confusing these is the most consequential modelling error in this area.
Is the graph directed and acyclic? A DAG permits topological sorting, and once sorted, shortest and longest paths are computable in O(V + E) by a single pass in that order — including longest paths, which are NP-hard on general graphs.
Answering those five questions usually leaves exactly one candidate.
- Unweighted shortest path is BFS, not Dijkstra
- Negative weights force Bellman-Ford; negative cycles need detection
- Shortest path joins two vertices; an MST spans all of them
- On a DAG, topological order makes even longest paths linear
Shortest Paths
BFS solves the unweighted case. Because the queue is FIFO, vertices are dequeued in order of increasing distance, so the first time a vertex is reached is by a shortest route. O(V + E), and no priority queue is involved.
Dijkstra's algorithm extends this to non-negative weights by replacing the queue with a priority queue keyed on tentative distance. It repeatedly extracts the closest unfinalised vertex, finalises its distance, and relaxes its outgoing edges. With a binary heap this is O((V + E) log V).
The correctness rests on a specific claim: when the closest unfinalised vertex is extracted, no shorter route to it can exist, because any alternative route would have to pass through another unfinalised vertex that is already further away — and adding non-negative edges cannot reduce the total.
That argument fails the moment an edge can be negative. A longer-looking route might later cross a negative edge and become shorter, so finalisation is premature and Dijkstra returns wrong answers silently. It does not loop or error; it just reports incorrect distances, which is why the precondition matters.
Bellman-Ford avoids finalisation entirely. It relaxes every edge, V−1 times. The bound is exact rather than arbitrary: a shortest path in a graph with V vertices contains at most V−1 edges, and each pass extends the correctly-computed prefix by at least one edge. The cost is O(V·E), notably slower than Dijkstra.
Its distinguishing capability is negative cycle detection. Run one additional pass; if any distance still improves, a negative cycle is reachable, since without one all distances would have stabilised. That extra pass is a two-line addition and the reason Bellman-Ford is used in currency-arbitrage and constraint problems.
Floyd-Warshall computes all pairs with three nested loops over an adjacency matrix, at O(V³). The insight is to consider each vertex k in turn as a permitted intermediate, asking whether routing through k improves any pair. It handles negative edges, and a negative value on the diagonal afterwards signals a negative cycle.
| Algorithm | Handles | Cost | Use when |
|---|---|---|---|
| BFS | Unweighted | O(V + E) | All edges cost the same |
| Dijkstra | Non-negative weights | O((V+E) log V) | Single source, no negatives |
| Bellman-Ford | Negative weights | O(V·E) | Negatives, or cycle detection |
| Floyd-Warshall | Negative weights | O(V³) | All pairs, dense graph |
| DAG shortest path | Any weights | O(V + E) | The graph is acyclic |
- Dijkstra finalises the closest vertex — valid only without negatives
- Bellman-Ford relaxes every edge V−1 times, the length of a longest path
- One extra Bellman-Ford pass detects a negative cycle
- Floyd-Warshall handles all pairs in O(V³) with three loops
Spanning Trees and Ordering
A minimum spanning tree is a subset of edges connecting every vertex with no cycles and the smallest possible total weight. It has exactly V−1 edges, and it exists only if the graph is connected.
Both standard algorithms are greedy, and both are justified by the cut property: for any partition of the vertices into two sets, the lightest edge crossing the partition belongs to some minimum spanning tree. Each algorithm applies this to a different cut.
Kruskal's algorithm sorts all edges by weight and adds each one whose endpoints are in different components, skipping those that would form a cycle. The component test is a union-find operation at near-constant cost, which is what makes the algorithm practical. Total O(E log E), dominated by the sort.
Prim's algorithm grows a single tree from an arbitrary start, repeatedly adding the cheapest edge leaving the tree, using a priority queue much as Dijkstra does. Total O((V + E) log V).
The choice follows density: Kruskal for sparse graphs, since it is driven by the edge count, and Prim for dense ones, where the vertex-centric loop wins. Both give a minimum spanning tree, though not necessarily the same one when weights tie.
The distinction from shortest paths deserves emphasis because it is examined often. An MST minimises the total weight of the whole tree; it does not minimise the distance between any specific pair, and the path between two vertices within an MST is frequently longer than their true shortest path. They answer different questions.
Topological sorting orders the vertices of a DAG so every edge points forward. Kahn's algorithm repeatedly removes a vertex of in-degree zero, adding it to the order and decrementing its neighbours; the DFS method appends each vertex on exit and reverses the result. Both are O(V + E).
Cycle detection comes free from either. If Kahn's algorithm finishes having emitted fewer than V vertices, the remainder lie on a cycle. The ordering is usually not unique — any order respecting the dependencies is valid, which matters when a problem asks for a specific one, such as the lexicographically smallest, requiring a min-heap in place of the plain queue.
- An MST has V−1 edges and both algorithms rest on the cut property
- Kruskal sorts edges and uses union-find; Prim grows with a heap
- An MST path between two vertices is usually not their shortest path
- Topological sorting works only on a DAG, so it detects cycles for free
Terms, operations, and practical uses
Algorithms
- Dijkstra'sFinds the shortest path from a starting node to all other nodes. Only works with non-negative edge weights.
- Bellman-FordFinds shortest paths and can handle negative edge weights. Can also detect negative weight cycles.
- Kruskal's / Prim'sAlgorithms to find the Minimum Spanning Tree (MST) of a weighted graph.
Key concepts
- Edge RelaxationThe process of updating the shortest known distance to a node if a shorter path is found via a neighboring node.
- Topological SortA linear ordering of vertices in a Directed Acyclic Graph (DAG) such that every directed edge U -> V means U comes before V.
- DAGDirected Acyclic Graph. A directed graph with no cycles, a requirement for Topological Sort and DP on graphs.
Data structures used
- Min-HeapUsed in Dijkstra's and Prim's algorithms to efficiently extract the next closest node or smallest edge.
- Disjoint SetUsed in Kruskal's algorithm to efficiently check if adding an edge will create a cycle.
- In-Degree ArrayUsed in Kahn's Algorithm for Topological Sort to track how many prerequisites a node has left.
Kahn's Algorithm for Topological Sort
from collections import deque
def topological_sort(n, edges):
in_degree = [0] * n
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# a short order means some node never reached in-degree 0: a cycle
return order if len(order) == n else []
names = ['A', 'B', 'C', 'D', 'E']
edges = [(0, 2), (1, 2), (2, 3), (2, 4)] # A->C, B->C, C->D, C->E
order = topological_sort(5, edges)
print('Order: [' + ', '.join(names[i] for i in order) + ']')#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> topologicalSort(int n, vector<pair<int, int>>& edges) {
vector<int> inDegree(n, 0);
vector<vector<int>> graph(n);
for (auto& e : edges) {
graph[e.first].push_back(e.second);
inDegree[e.second]++;
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) q.push(i);
}
vector<int> order;
while (!q.empty()) {
int node = q.front();
q.pop();
order.push_back(node);
for (int neighbor : graph[node]) {
if (--inDegree[neighbor] == 0) q.push(neighbor);
}
}
// a short order means some node never reached in-degree 0: a cycle
if ((int)order.size() != n) return {};
return order;
}
int main() {
string names[] = {"A", "B", "C", "D", "E"};
vector<pair<int, int>> edges = {{0, 2}, {1, 2}, {2, 3}, {2, 4}};
vector<int> order = topologicalSort(5, edges);
cout << "Order: [";
for (size_t i = 0; i < order.size(); i++) {
cout << names[order[i]] << (i + 1 < order.size() ? ", " : "");
}
cout << "]\n";
}import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
class Main {
static List<Integer> topologicalSort(int n, int[][] edges) {
int[] inDegree = new int[n];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
inDegree[e[1]]++;
}
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) queue.add(i);
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int neighbor : graph.get(node)) {
if (--inDegree[neighbor] == 0) queue.add(neighbor);
}
}
// a short order means some node never reached in-degree 0: a cycle
return order.size() == n ? order : new ArrayList<>();
}
public static void main(String[] args) {
String[] names = {"A", "B", "C", "D", "E"};
int[][] edges = {{0, 2}, {1, 2}, {2, 3}, {2, 4}};
List<Integer> order = topologicalSort(5, edges);
StringBuilder sb = new StringBuilder("Order: [");
for (int i = 0; i < order.size(); i++) {
sb.append(names[order.get(i)]);
if (i + 1 < order.size()) sb.append(", ");
}
System.out.println(sb.append("]"));
}
}Step through it
Running on DAG: A→C, B→C, C→D, C→E
Read all 12 Steps
- Read the dependency graph Five tasks with edges A→C, B→C, C→D, C→E. An edge u→v means u must finish before v starts, so a valid order is any linear sequence respecting every arrow.
- Count in-degrees In-degree is the number of unmet prerequisites. A and B have none. C waits on both A and B, so its in-degree is 2. D and E each wait only on C.
- Seed the queue with in-degree 0 A and B depend on nothing, so they are safe to emit immediately and both enter the ready queue. A graph with no in-degree-0 node at this point is already proven cyclic.
- Emit A Pop A from the front of the queue and append it to the order. Kahn's algorithm never backtracks — once a node is emitted, its position is final.
- Relax A→C A is placed, so one of C's prerequisites is satisfied. C's in-degree drops from 2 to 1. It still waits on B, so it does not enter the queue yet.
- Emit B B is next off the queue and joins the order. Both source nodes are now placed and the queue is momentarily empty — but the algorithm is not finished, because relaxing B's edges may refill it.
- Relax B→C, C becomes ready C's in-degree drops from 1 to 0, so every prerequisite is met and C enters the queue. This is the moment a node becomes eligible: the instant its last incoming edge is consumed.
- Emit C C leaves the queue and takes third place in the order, after both nodes it depended on.
- Relax C→D and C→E Removing C satisfies the only prerequisite of both D and E, so their in-degrees fall to 0 together and both enter the queue. Two nodes are now simultaneously ready, which is why topological order is not unique.
- Emit D D pops first because it was enqueued first. Swapping D and E here would produce an equally valid answer — any order the arrows permit is correct.
- Emit E E completes the order and the queue drains to empty, so the while loop exits. Every node has now been emitted exactly once.
- Five of five emitted, so no cycle The count check is the cycle detector. All 5 nodes were emitted, so the graph is a DAG. Had a cycle existed, its nodes would never have reached in-degree 0, the queue would have emptied early, and the short order would prove the cycle without any extra traversal.
A Decision Procedure
Putting it together as a sequence to run on an unfamiliar problem.
Model first. Decide what a vertex is and what an edge is, and whether edges are directed. This step is where most graph problems are actually solved — grid cells with adjacency, words differing by one letter, tasks with prerequisites, and states with transitions are all graphs once named as such.
Then choose the representation. An adjacency list at O(V + E) is right for nearly all real graphs, which are sparse. An adjacency matrix at O(V²) is right only for dense graphs or for Floyd-Warshall. Choosing a matrix for a sparse graph turns an O(V + E) traversal into O(V²), which is the most common performance error here.
Then match the question. Can I reach it — BFS or DFS. Shortest path, unweighted — BFS. Shortest path, non-negative weights — Dijkstra. Negative weights or cycle detection — Bellman-Ford. All pairs, dense — Floyd-Warshall. Connect everything cheaply — Kruskal or Prim. Valid ordering under dependencies — topological sort. Connected components — DFS or union-find. Does a cycle exist — DFS with colours for directed graphs, union-find for undirected ones.
Two implementation details cause a disproportionate share of bugs regardless of algorithm. Mark vertices visited when they are enqueued, not when they are dequeued — marking late lets a vertex enter the queue several times and can make a traversal quadratic. And restart the traversal from every unvisited vertex when the graph may be disconnected, otherwise entire components are silently missed.
A note on scale: these algorithms all assume the graph fits in memory. Beyond that, the field changes character — external-memory and distributed frameworks such as Pregel's vertex-centric model take over, and the algorithms are reformulated rather than merely scaled.
- Model the vertices and edges first — that is most of the work
- Adjacency list unless the graph is genuinely dense
- Mark visited on enqueue, not on dequeue
- Restart from every unvisited vertex or miss whole components