DSA · Lesson 17 of 20 · 5 min
Advanced Graph Algorithms: Shortest Paths & MST
Know which algorithm to pick for pathfinding and how to defend your choice.
After this, you'll know exactly when to use Dijkstra's versus Bellman-Ford, and how to explain the trade-offs for finding the cheapest network route or the minimum set of dependencies. These aren't just abstract puzzles; they model real system design problems.
Choosing the Right Shortest Path Algorithm
The "shortest path" problem isn't one problem, but a family. Your first job in an interview is to clarify the constraints. Are you finding a path from one node to another (single-source), or between all of them (all-pairs)? Can the path costs (weights) be negative?
Your decision process should be simple:
-
Dijkstra's Algorithm: This is your default for single-source shortest paths. It's fast and efficient. Its one major limitation is that it cannot handle negative edge weights. If all weights are zero or positive, use Dijkstra's. Its time complexity is O((V+E)logV) with a proper priority queue.
-
Bellman-Ford Algorithm: Use this when you have negative edge weights. It's slower than Dijkstra's at O(V*E), but it's more versatile. It can also detect negative cycles—a loop you can traverse infinitely to get a shorter and shorter path, which is usually an error condition.
-
Floyd-Warshall Algorithm: Use this when you need to find the shortest paths between all pairs of nodes. Its O(V^3) complexity makes it too slow for large, sparse graphs, but it's simple to implement and effective for small, dense ones. It can handle negative weights but not negative cycles.
The trap: A candidate hears "shortest path" and immediately starts coding Dijkstra's. The interviewer then adds a constraint about negative weights, and the candidate's solution is now incorrect. Always clarify the constraints on edge weights before you write a line of code.
How Dijkstra's Algorithm Works
Dijkstra's finds the shortest path from a starting node to all other nodes in a weighted graph. It works by maintaining a set of visited nodes and always exploring the next closest unvisited node.
The core of the algorithm is a min-priority queue. This data structure stores the nodes to visit, prioritized by their current known shortest distance from the source. At each step, you extract the node with the minimum distance, "finalize" that distance, and then update the distances of its neighbors if you've found a shorter path to them through the current node.
The following code implements Dijkstra's. Notice it uses Array.sort() to simulate a priority queue. This is simple to write but inefficient, leading to a time complexity closer to O(V*E).
The trap: In an interview, you can use this simplified version to get the logic across, but you must state that a production implementation would use a min-heap. Explain that a min-heap provides O(logV) for insertions and extractions, which is what gets you to the optimal O((V+E)logV) complexity.
type AdjacencyList = Map<number, { node: number; weight: number }[]>;
function dijkstra(graph: AdjacencyList, startNode: number): Map<number, number> {
const distances = new Map<number, number>();
// In a real interview, state you'd use a Min-Heap for this.
const priorityQueue: { node: number; dist: number }[] = [];
const visited = new Set<number>();
for (const node of graph.keys()) {
distances.set(node, Infinity);
}
distances.set(startNode, 0);
priorityQueue.push({ node: startNode, dist: 0 });
while (priorityQueue.length > 0) {
// This sort is O(N log N) where N is PQ size. A heap is O(log N).
priorityQueue.sort((a, b) => a.dist - b.dist);
const { node: currentNode } = priorityQueue.shift()!;
if (visited.has(currentNode)) {
continue;
}
visited.add(currentNode);
const currentDist = distances.get(currentNode)!;
for (const edge of graph.get(currentNode) || []) {
const { node: neighborNode, weight } = edge;
const newDist = currentDist + weight;
if (newDist < distances.get(neighborNode)!) {
distances.set(neighborNode, newDist);
priorityQueue.push({ node: neighborNode, dist: newDist });
}
}
}
return distances;
}
Minimum Spanning Trees (MSTs)
Don't confuse MSTs with shortest paths. A shortest path finds the cheapest route between two points. An MST finds the cheapest way to connect all points in a network. The result is a tree (a graph with no cycles) that includes every vertex, where the total sum of edge weights is minimized.
Think of connecting houses to a water supply. You don't need the shortest path from the reservoir to each house; you need the cheapest overall layout of pipes that serves everyone.
There are two main algorithms for this:
-
Prim's Algorithm: Starts at an arbitrary node and "grows" the MST by adding the cheapest edge that connects a vertex in the tree to a vertex outside the tree. It's greedy and works much like Dijkstra's, often also using a priority queue. It's generally preferred for dense graphs (where the number of edges is close to V^2).
-
Kruskal's Algorithm: Sorts all edges by weight, from cheapest to most expensive. It then iterates through the sorted edges, adding each one to the MST as long as it doesn't form a cycle. To efficiently detect cycles, it uses a Union-Find data structure. It's often better for sparse graphs.
You probably won't be asked to implement both. Know the difference: Prim's grows from a single point, while Kruskal's pieces together the cheapest connections from all over the graph.
Where This Shows Up in Frontend Interviews
While you're not routing network packets in the browser, graph problems model many frontend challenges.
-
Dependency Resolution: A build tool like Webpack or Vite constructs a dependency graph. Finding the shortest path can identify how a specific library is being included. An MST could help identify a core set of shared dependencies in a monorepo. The problem Min Cost to Connect All Points is a classic MST problem.
-
UI Navigation: Imagine a complex SPA where views can transition to other views. This is a directed graph. A question like "What is the minimum number of clicks to get from the homepage to the checkout confirmation page?" is a shortest path problem on an unweighted graph, solvable with BFS (which is just Dijkstra's on a graph where all edge weights are 1).
-
Network Latency: If you're fetching data from multiple services with known latencies, you can model this as a graph. A problem like Network Delay Time asks for the time it takes for a signal to reach all nodes, which is a direct application of Dijkstra's.
Try it
Refactor the Dijkstra's code provided to use a proper Min-Heap for its priority queue instead of Array.sort(). You don't need a full-featured library; just implement the basic insert and extractMin methods. Explain why this changes the overall time complexity.
Next: Dynamic Programming II: Tabulation & Frontend Patterns
Lock it in — apply this lesson under interview conditions.