Topic 71 of 78
Dijkstra's Algorithm
Overview
BFS finds the shortest path in an unweighted graph (every road takes 1 minute). But what if roads have different lengths or traffic? Dijkstra's Algorithm finds the shortest path in a Weighted Graph (where edges have costs/weights). It uses a PriorityQueue (Min-Heap) to always greedily explore the cheapest available path first.
Syntax
By constantly picking the cheapest node from the PriorityQueue, Dijkstra guarantees that the first time a node is popped, we have found the absolute cheapest path to it.
Dijkstra's Shortest Path
java
// Assuming a Node class with 'id' and 'cost'
public int dijkstra(Map<Integer, List<int[]>> graph, int start, int target) {
// PriorityQueue to always pop the node with the lowest total cost
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // [node, totalCost]
Set<Integer> visited = new HashSet<>();
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int node = curr[0];
int totalCost = curr[1];
if (node == target) return totalCost; // Found shortest path!
if (visited.contains(node)) continue; // Already found a cheaper path to this node
visited.add(node);
for (int[] edge : graph.getOrDefault(node, new ArrayList<>())) {
int neighbor = edge[0];
int edgeWeight = edge[1];
if (!visited.contains(neighbor)) {
pq.offer(new int[]{neighbor, totalCost + edgeWeight});
}
}
}
return -1; // Path not found
}Common Pitfalls
- Adding a node to the `visited` set when pushing it to the PriorityQueue instead of when POPPING it. You only lock in the shortest path when the node is popped from the PQ.
- Using Dijkstra on graphs with negative weights (like financial arbitrage graphs). It will fail.
Interview Tips
- Dijkstra is essentially BFS, but using a PriorityQueue instead of a standard Queue.
Real-World Example
Google Maps routing. Calculating the fastest driving route between two cities based on speed limits and distance.
example
java
// Google Maps uses A* Search, which is basically Dijkstra with a heuristic guess to speed it up.