The Algorithm That Powers Every “Get Directions” Button
Dijkstra Algorithm
DSA for Android Developers Episode 4
It’s 2 AM. You’re at a party in an unfamiliar neighborhood, your phone battery is at 5%, and you need to find the quickest route home before it dies. You open Google Maps, hit “Directions,” and within milliseconds, you have your optimal route.
Behind that instant result is one of computer science’s most elegant algorithms: Dijkstra’s algorithm. Created in 1956 by Edsger Dijkstra (who reportedly designed it in 20 minutes while shopping with his fiancée), this algorithm doesn’t just power your GPS, it’s the foundation of internet routing, game AI, and even social network analysis.
Today, let’s uncover how this algorithm thinks about paths the same way you do just much, much faster.
The Shortest Path Problem: It’s Not Just About Distance
Before diving into Dijkstra’s brilliance, let’s understand what we’re solving. The shortest path problem asks: “What’s the best way to get from point A to point B?”
But “best” doesn’t always mean shortest distance. It could mean:
- 🚗 Fastest route (considering traffic)
- 💰 Cheapest path (tolls and gas)
- 🔋 Most energy-efficient (for EVs)
- 🎮 Safest route (in game pathfinding
Dijkstra’s algorithm finds the optimal path for any definition of “cost”as long as all costs are non-negative.
How Dijkstra’s Algorithm Thinks
The Mental Model: Expanding Ripples in a Pond
Imagine dropping a stone in a still pond. The ripples expand outward in perfect circles, reaching the nearest points first, then gradually reaching farther points. Dijkstra’s algorithm works exactly like this , it explores the graph in expanding “circles” of distance from the starting point.
The Brilliant Insight
Dijkstra had one key realization: If you always explore the nearest unvisited vertex next, you’ll never need to revise its distance later.
This is profound. It means once you’ve calculated the shortest path to a vertex, you’re done with it forever. No backsies, no second-guessing.
The Step-by-Step Process
Let’s follow Dijkstra’s algorithm finding the shortest path in a small city:
Notice how we built the solution by always choosing the closest unvisited vertex — like a careful explorer mapping unknown territory.
The Implementation: Priority Queue Magic
The key to efficient Dijkstra’s is using a priority queue (min-heap) to always get the nearest unvisited vertex quickly.
import java.util.*;
public class DijkstraAlgorithm {
static class Edge {
int destination;
int weight;
Edge(int destination, int weight) {
this.destination = destination;
this.weight = weight;
}
}
static class Node implements Comparable<Node> {
int vertex;
int distance;
Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.distance, other.distance);
}
}
static class Graph {
private int vertices;
private List<List<Edge>> adjacencyList;
public Graph(int vertices) {
this.vertices = vertices;
this.adjacencyList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new ArrayList<>());
}
}
public void addEdge(int source, int destination, int weight) {
adjacencyList.get(source).add(new Edge(destination, weight));
// For undirected graph, add reverse edge
adjacencyList.get(destination).add(new Edge(source, weight));
}
public int[] dijkstra(int source) {
// Initialize distances
int[] distances = new int[vertices];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[source] = 0;
// Track visited vertices
boolean[] visited = new boolean[vertices];
// Priority queue to get minimum distance vertex
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(source, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int u = current.vertex;
// Skip if already visited
if (visited[u]) continue;
visited[u] = true;
// Explore neighbors
for (Edge edge : adjacencyList.get(u)) {
int v = edge.destination;
int weight = edge.weight;
// Relaxation step
if (distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
pq.offer(new Node(v, distances[v]));
}
}
}
return distances;
}
// Method to find actual path, not just distances
public List<Integer> dijkstraWithPath(int source, int destination) {
int[] distances = new int[vertices];
int[] parent = new int[vertices];
Arrays.fill(distances, Integer.MAX_VALUE);
Arrays.fill(parent, -1);
distances[source] = 0;
boolean[] visited = new boolean[vertices];
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(source, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int u = current.vertex;
if (visited[u]) continue;
visited[u] = true;
// Early termination if we reached destination
if (u == destination) break;
for (Edge edge : adjacencyList.get(u)) {
int v = edge.destination;
int weight = edge.weight;
if (distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
parent[v] = u;
pq.offer(new Node(v, distances[v]));
}
}
}
// Reconstruct path
List<Integer> path = new ArrayList<>();
if (distances[destination] == Integer.MAX_VALUE) {
return path; // No path exists
}
int current = destination;
while (current != -1) {
path.add(0, current);
current = parent[current];
}
return path;
}
}
public static void main(String[] args) {
// Example: Navigation in a city
Graph cityMap = new Graph(6);
String[] locations = {"Home", "Office", "Gym", "Store", "Park", "Restaurant"};
// Add roads with travel times (in minutes)
cityMap.addEdge(0, 1, 10); // Home - Office
cityMap.addEdge(0, 2, 15); // Home - Gym
cityMap.addEdge(1, 3, 12); // Office - Store
cityMap.addEdge(1, 4, 15); // Office - Park
cityMap.addEdge(2, 3, 10); // Gym - Store
cityMap.addEdge(3, 4, 2); // Store - Park
cityMap.addEdge(3, 5, 10); // Store - Restaurant
cityMap.addEdge(4, 5, 10); // Park - Restaurant
// Find shortest paths from Home
int[] distances = cityMap.dijkstra(0);
System.out.println("Shortest times from Home:");
for (int i = 0; i < locations.length; i++) {
System.out.printf("To %s: %d minutes\n", locations[i], distances[i]);
}
// Find actual path from Home to Restaurant
List<Integer> path = cityMap.dijkstraWithPath(0, 5);
System.out.print("\nBest route to Restaurant: ");
for (int i = 0; i < path.size(); i++) {
System.out.print(locations[path.get(i)]);
if (i < path.size() - 1) System.out.print(" → ");
}
System.out.println("\nTotal time: " + distances[5] + " minutes");
}
}Time Complexity: O((V + E) log V) with a binary heap, where V is vertices and E is edges.
Real-World Magic: Where Dijkstra Dominates
1. GPS Navigation Systems
Every time you use Google Maps, Waze, or Apple Maps, you’re using a variant of Dijkstra’s algorithm. Modern systems enhance it with:
- A algorithm*: Dijkstra’s with heuristics for faster pathfinding
- Contraction Hierarchies: Preprocessing for lightning-fast queries
- Real-time traffic: Dynamic edge weights that change based on conditions
2. Network Routing Protocols
Internet routers use Dijkstra’s algorithm in protocols like OSPF (Open Shortest Path First) to find the best path for data packets. Your Netflix stream finds its way to you thanks to Dijkstra!
3. Flight Search Engines
When Kayak or Google Flights finds you the cheapest route from New York to Bali with connections, they’re using Dijkstra’s variants to search through millions of possible combinations.
4. Game AI Pathfinding
From Pac-Man ghosts to StarCraft units, game AI uses Dijkstra’s (or its cousin A*) to navigate game worlds intelligently.
The Relaxation Concept: The Heart of Dijkstra’s
The core operation in Dijkstra’s is called “relaxation” — a weird name for a simple idea:
Think of it like this: You thought the best way to the store was a 20-minute direct route. But then you discover going via the park takes only 15 minutes total. You “relax” (improve) your estimate.
Common Variations and Optimizations
1. Bidirectional Dijkstra
Start from both source and destination, meet in the middle. This can be nearly twice as fast for point-to-point queries.
2. Dijkstra with Early Termination
If you only need the path to one destination, stop once you’ve visited it:
3. Multi-Source Dijkstra
Find shortest paths from multiple sources simultaneously. Perfect for problems like “find the nearest hospital.”
4. Dijkstra on Dynamic Graphs
When edge weights change (like traffic updates), you can use Dynamic Shortest Path algorithms to update paths efficiently without recalculating everything.
When Dijkstra’s Fails: The Negative Weight Problem
Dijkstra’s has one Achilles’ heel: negative edge weights. Why? Because its fundamental assumption : that we never need to revisit a “settled” vertex breaks down.
Example of failure:
For graphs with negative weights, use Bellman-Ford algorithm instead.
Practice Problems: Level Up Your Skills
Ready to master Dijkstra’s? Try these:
- LeetCode #743: Network Delay Time
- LeetCode #787: Cheapest Flights Within K Stops
- LeetCode #1514: Path with Maximum Probability
- CSES: Shortest Routes I & II
- AtCoder: Various shortest path problems
Start with basic implementation, then try:
- Finding k shortest paths
- Dijkstra’s on a grid (2D maze)
- Modified Dijkstra’s with constraints
Wrapping Up: The Algorithm That Connected the World
Dijkstra’s algorithm is more than just a pathfinding tool, it’s a lens through which we can understand optimization, decision-making, and the power of greedy algorithms done right.
Every time you get directions, send a message across the internet, or watch an AI navigate a game world, remember Edsger Dijkstra’s 20-minute shopping trip insight: sometimes the best way forward is to always take the next best step.
In a world full of complex paths and endless possibilities, Dijkstra’s algorithm reminds us that finding our way doesn’t require seeing the whole journey, just the wisdom to take the best next step.
Enjoyed this journey through our Algorithm series for Android Devs? Follow for more algorithms that shape our digital world. Next up in DSA series: “Bellman-Ford Algorithm”
