Dijkstra's Algorithm
Overview
While Breadth-First Search (BFS) mathematically guarantees finding the shortest path in an unweighted graph, it completely fails if the edges have different weights (e.g., roads with different speed limits, traffic, or travel times).
Dijkstra's Algorithm is the legendary solution for finding the absolute shortest path from a starting node to all other nodes in a Weighted Graph.
It achieves this by replacing the standard BFS Queue with a Priority Queue (Min-Heap). Instead of blindly pulling the oldest node from the queue, Dijkstra's always pulls the node that currently has the lowest total cumulative travel cost from the starting position. It prioritizes exploring 'cheap' paths first, aggressively abandoning paths that prove to be too expensive. Because it always explores the cheapest available option next, the first time it extracts your destination node from the queue, it has mathematically proven that no cheaper route can possibly exist.
Syntax
import java.util.*;
public class Dijkstra {
class Edge {
int target, weight;
Edge(int target, int weight) { this.target = target; this.weight = weight; }
}
class Route {
int node, totalCost;
Route(int node, int totalCost) { this.node = node; this.totalCost = totalCost; }
}
Map<Integer, List<Edge>> graph = new HashMap<>();
public int shortestPath(int start, int destination) {
// Min-Heap prioritizes routes with the LOWEST total cost
PriorityQueue<Route> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.totalCost, b.totalCost));
// Tracks the minimum known cost to reach any specific node
Map<Integer, Integer> minCostMap = new HashMap<>();
pq.offer(new Route(start, 0));
minCostMap.put(start, 0);
while (!pq.isEmpty()) {
// Extract the absolute cheapest known route
Route current = pq.poll();
// If we reached destination, we guarantee it's the absolute cheapest path
if (current.node == destination) return current.totalCost;
// Optimization: If we already found a cheaper way to this node previously,
// ignore this outdated, expensive route.
if (current.totalCost > minCostMap.getOrDefault(current.node, Integer.MAX_VALUE)) {
continue;
}
// Evaluate all neighbors extending from this node
for (Edge edge : graph.getOrDefault(current.node, new ArrayList<>())) {
int newCost = current.totalCost + edge.weight;
// If this new route is strictly cheaper than any previously known route
if (newCost < minCostMap.getOrDefault(edge.target, Integer.MAX_VALUE)) {
minCostMap.put(edge.target, newCost); // Update best known cost
pq.offer(new Route(edge.target, newCost)); // Enqueue new route
}
}
}
return -1; // Path not found
}
}Common Pitfalls
- Using a standard Queue instead of a PriorityQueue. This downgrades the algorithm to a terrible BFS that will find incorrect paths in weighted graphs.
- Failing to skip outdated, higher-cost routes in the PriorityQueue. Because you can enqueue the same node multiple times (as you find new routes to it), you must
continue;if the popped route is more expensive than your current known minimum, otherwise you cause exponential time bloat. - Negative edge weights. Dijkstra's fundamentally assumes that adding an edge always increases the total cost. If your graph has negative weights (e.g., getting paid to travel a road), Dijkstra's will fail and return incorrect results. You must use the Bellman-Ford algorithm instead.
Interview Questions
The Bellman-Ford algorithm. It handles negative weights and can successfully detect negative weight cycles, though it runs much slower at O(V * E) time complexity compared to Dijkstra's O((V + E) log V).
O((V + E) log V). Every vertex is processed, every edge is evaluated, and enqueuing/dequeuing from the Priority Queue takes O(log V) time.
Real-World Example
GPS Navigation Systems (Google Maps, Waze). When routing you from Home to Work, the map is a massive graph. Intersections are nodes. Roads are edges. The 'weight' of the edge is the estimated travel time (factoring in speed limits and traffic). Google Maps runs variations of Dijkstra's (specifically A* Search) to guarantee finding the fastest route to your destination.
// Conceptual GPS Routing
public Route navigate(Intersection start, Intersection destination) {
PriorityQueue<Path> pq = new PriorityQueue<>((a, b) -> a.estimatedTime - b.estimatedTime);
pq.offer(new Path(start, 0));
while (!pq.isEmpty()) {
Path current = pq.poll();
if (current.location.equals(destination)) return current;
for (Road road : current.location.getConnectingRoads()) {
int newTime = current.estimatedTime + road.calculateTrafficDelay();
// Compare with minCostMap, add to PriorityQueue...
}
}
return null;
}Check Your Knowledge
Test your understanding of Dijkstra's Algorithm with these quick questions.