Imagine you are using a map app to travel from your home to your college.
There are many possible routes. Some have fewer turns, some pass through more junctions, but what you really care about is the total distance (or total travel time).
A route with 3 roads of 2 km each (6 km total) is better than a route with 1 road of 10 km.
In the BFS chapter, we learned how to find the path with the fewest edges. But when roads have different lengths, the fewest edges is not always the shortest distance.
This is exactly the problem that Dijkstra's Algorithm solves.
Dijkstra's Algorithm finds the shortest distance from one source vertex to every other vertex in a weighted graph where all edge weights are non-negative.
It was designed by the Dutch computer scientist Edsger W. Dijkstra in 1956 (and published in 1959), and it is still one of the most frequently asked graph algorithms in coding interviews and placement tests.
Why BFS Is Not Enough
Consider this weighted graph:
10
A ────────── C
│ │
2 │ │ 1
│ │
B ────────── D
3Suppose we want to go from A to C.
BFS counts edges, so it picks:
A → C (1 edge, cost 10)But the cheaper route is:
A → B → D → C (3 edges, cost 2 + 3 + 1 = 6)So:
Unweighted graph (all edges equal) → BFS
Weighted graph, non-negative edges → DijkstraSingle-Source Shortest Path
Dijkstra's algorithm solves the single-source shortest path problem.
Single-source shortest path: given one starting vertex (the source), find the minimum total weight needed to reach every other vertex.
The output is usually a dist[] array:
dist[v] = length of the shortest path from source to vIf a vertex cannot be reached at all, its distance stays infinity.
The Core Idea
Dijkstra's algorithm keeps a tentative distance for every vertex.
At the start:
dist[source] = 0
dist[every other vertex] = ∞Then it repeats one simple step:
Pick the unvisited vertex with the smallest tentative distance, mark it as final, and use it to improve the distances of its neighbors.
Why can we mark it as final?
Because all edge weights are non-negative. If the closest unvisited vertex is at distance d, any other route to it would have to pass through some other unvisited vertex that is already at distance ≥ d, and adding more non-negative edges can never make it smaller than d.
This "always pick the closest one" choice makes Dijkstra a greedy algorithm.
Relaxation
The operation that "improves" a neighbor's distance is called relaxation. It is the heart of every shortest-path algorithm.
Relaxing an edge u → v with weight w means: if going through u gives a shorter path to v, update dist[v].
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = uExample:
dist[u] = 3
w = 2
dist[v] = 9
3 + 2 = 5 < 9 → dist[v] becomes 5If dist[u] + w is not smaller, nothing changes.
The parent[] array remembers which vertex we came from, so we can rebuild the actual path later.
Dijkstra Step by Step
Let's run Dijkstra on this undirected graph with source 0:
4
0 ─────── 1
│ / │
1 │ 2/ │ 1
│ / │
2 ─────── 3 ─────── 4
5 3Edges:
0 - 1 : 4
0 - 2 : 1
2 - 1 : 2
1 - 3 : 1
2 - 3 : 5
3 - 4 : 3We use a min priority queue that stores pairs (node, distance) and always gives us the pair with the smallest distance.
Start
dist = [0, ∞, ∞, ∞, ∞]
PQ = (0,0)Step 1: Pop (0, 0)
Mark 0 as visited. Relax its edges:
0 → 1 : 0 + 4 = 4 < ∞ → dist[1] = 4
0 → 2 : 0 + 1 = 1 < ∞ → dist[2] = 1
dist = [0, 4, 1, ∞, ∞]
PQ = (2,1) (1,4)Step 2: Pop (2, 1)
Node 2 is the closest unvisited node. Mark it visited.
2 → 1 : 1 + 2 = 3 < 4 → dist[1] = 3
2 → 3 : 1 + 5 = 6 < ∞ → dist[3] = 6
dist = [0, 3, 1, 6, ∞]
PQ = (1,3) (1,4) (3,6)Notice that (1,4) is still in the queue even though we found a better distance for node 1. Java's PriorityQueue has no efficient "decrease key" operation, so we simply add a new pair and ignore the old one later.
Step 3: Pop (1, 3)
Mark 1 visited.
1 → 3 : 3 + 1 = 4 < 6 → dist[3] = 4
dist = [0, 3, 1, 4, ∞]
PQ = (1,4) (3,4) (3,6)Step 4: Pop (1, 4)
Node 1 is already visited, so this is a stale entry. Skip it.
Step 5: Pop (3, 4)
Mark 3 visited.
3 → 4 : 4 + 3 = 7 < ∞ → dist[4] = 7
dist = [0, 3, 1, 4, 7]
PQ = (3,6) (4,7)Step 6: Pop (3, 6)
Stale entry. Skip.
Step 7: Pop (4, 7)
Mark 4 visited. It has no unvisited neighbors. The queue is now empty.
Final answer:
Node: 0 1 2 3 4
Distance: 0 3 1 4 7(When two pairs have the same distance, such as (1,4) and (3,4), the priority queue may return either one first. The final distances are the same either way.)
The Algorithm
Dijkstra(source):
dist[all] = ∞
dist[source] = 0
add (source, 0) to min priority queue
while priority queue is not empty:
(u, d) = remove the pair with smallest d
if u is already visited:
continue // stale entry
mark u as visited
for each edge (u → v, weight w):
if v is not visited and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
add (v, dist[v]) to priority queueRepresenting a Weighted Graph in Java
In the Graph Representation chapter, we stored a weighted adjacency list using a small Edge class with a destination and a weight. That works perfectly here too.
In competitive programming and interviews, a shorter alternative is common: store each edge as an int[] of size 2.
// edge = {neighbor, weight}
ArrayList<ArrayList<int[]>> graph = new ArrayList<>();Adding an undirected edge u - v with weight w:
graph.get(u).add(new int[]{v, w});
graph.get(v).add(new int[]{u, w});For a directed edge, add only the first line.
Dijkstra in Java
Here is a complete program for the graph we traced above. We add one extra vertex 5 with no edges to show how unreachable vertices are handled, and we also print the actual shortest path using parent[].
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
class Main {
static final int INF = Integer.MAX_VALUE;
static void addEdge(
ArrayList<ArrayList<int[]>> graph,
int u,
int v,
int w
) {
graph.get(u).add(new int[]{v, w});
graph.get(v).add(new int[]{u, w});
}
static int[] dijkstra(
int source,
ArrayList<ArrayList<int[]>> graph,
int[] parent
) {
int n = graph.size();
int[] dist = new int[n];
Arrays.fill(dist, INF);
Arrays.fill(parent, -1);
boolean[] visited = new boolean[n];
// Each entry is {node, distance}
PriorityQueue<int[]> pq =
new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
dist[source] = 0;
pq.add(new int[]{source, 0});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int u = top[0];
if (visited[u]) {
continue; // stale entry, u is already final
}
visited[u] = true;
for (int[] edge : graph.get(u)) {
int v = edge[0];
int w = edge[1];
if (!visited[v] && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
parent[v] = u;
pq.add(new int[]{v, dist[v]});
}
}
}
return dist;
}
static String path(int target, int[] parent) {
ArrayList<Integer> nodes = new ArrayList<>();
for (int v = target; v != -1; v = parent[v]) {
nodes.add(0, v);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < nodes.size(); i++) {
if (i > 0) {
sb.append(" -> ");
}
sb.append(nodes.get(i));
}
return sb.toString();
}
public static void main(String[] args) {
int vertices = 6;
ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
addEdge(graph, 0, 1, 4);
addEdge(graph, 0, 2, 1);
addEdge(graph, 2, 1, 2);
addEdge(graph, 1, 3, 1);
addEdge(graph, 2, 3, 5);
addEdge(graph, 3, 4, 3);
// Vertex 5 has no edges, so it is unreachable
int[] parent = new int[vertices];
int[] dist = dijkstra(0, graph, parent);
for (int v = 0; v < vertices; v++) {
if (dist[v] == INF) {
System.out.println("Node " + v + " : unreachable");
} else {
System.out.println(
"Node " + v + " : " + dist[v]
+ " path: " + path(v, parent)
);
}
}
}
}Output:
Node 0 : 0 path: 0
Node 1 : 3 path: 0 -> 2 -> 1
Node 2 : 1 path: 0 -> 2
Node 3 : 4 path: 0 -> 2 -> 1 -> 3
Node 4 : 7 path: 0 -> 2 -> 1 -> 3 -> 4
Node 5 : unreachableUnderstanding the Important Lines
The Min Priority Queue
PriorityQueue<int[]> pq =
new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));The comparator orders pairs by a[1], the distance. So poll() always returns the closest pair. We use Integer.compare instead of a[1] - b[1] because subtraction can overflow for very large values.
Skipping Stale Entries
if (visited[u]) {
continue;
}Because we add a new pair every time a distance improves, the same node can appear in the queue many times. Only the first time it is popped (with its smallest distance) matters.
Another common way to write the same check is:
int d = top[1];
if (d > dist[u]) {
continue; // this pair is outdated
}Both versions work correctly for non-negative weights.
Rebuilding the Path
To get the path to 4, we follow parents backwards:
4 → parent 3 → parent 1 → parent 2 → parent 0 → parent -1 (stop)
Reverse it: 0 → 2 → 1 → 3 → 4Time and Space Complexity
With an adjacency list and a binary-heap priority queue (Java's PriorityQueue):
Every edge can cause at most one push into the queue, so the queue holds at most
O(E)entries.Each push and pop costs
O(log E), andlog E ≤ log V² = 2 log V, so this is the same asO(log V).
Time → O((V + E) log V)
Space → O(V + E)You will often see this written as O(E log V), which is the same thing for a connected graph.
The O(V²) Version for Dense Graphs
Dijkstra can also be written without a priority queue. In each round, we simply scan all vertices to find the closest unvisited one.
import java.util.Arrays;
class Main {
static final int INF = Integer.MAX_VALUE;
// O(V^2) Dijkstra using an adjacency matrix (0 = no edge)
static int[] dijkstra(int source, int[][] matrix) {
int n = matrix.length;
int[] dist = new int[n];
Arrays.fill(dist, INF);
boolean[] visited = new boolean[n];
dist[source] = 0;
for (int round = 0; round < n; round++) {
// 1. Pick the unvisited node with the smallest distance
int u = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && (u == -1 || dist[i] < dist[u])) {
u = i;
}
}
if (dist[u] == INF) {
break; // remaining nodes are unreachable
}
visited[u] = true;
// 2. Relax all edges going out of u
for (int v = 0; v < n; v++) {
if (matrix[u][v] != 0 && !visited[v]
&& dist[u] + matrix[u][v] < dist[v]) {
dist[v] = dist[u] + matrix[u][v];
}
}
}
return dist;
}
public static void main(String[] args) {
int[][] matrix = {
{0, 4, 1, 0, 0},
{4, 0, 2, 1, 0},
{1, 2, 0, 5, 0},
{0, 1, 5, 0, 3},
{0, 0, 0, 3, 0}
};
System.out.println(Arrays.toString(dijkstra(0, matrix)));
}
}Output:
[0, 3, 1, 4, 7]This version runs in O(V²) time. (Using 0 to mean "no edge" only works here because this example has no zero-weight edges.)
Version | Time | Best for |
|---|---|---|
Priority queue + adjacency list | O((V + E) log V) | Sparse graphs (most interview problems) |
Simple array scan + matrix | O(V²) | Very dense graphs where E is close to V² |
Why Dijkstra Fails with Negative Edges
Dijkstra's key assumption is: once a vertex is popped, its distance is final. Negative edges break this assumption.
Consider this directed graph:
0 → 1 : 2
0 → 2 : 5
2 → 1 : -4
1 → 3 : 1The true shortest distances are:
dist[1] = 0 → 2 → 1 = 5 + (-4) = 1
dist[3] = 0 → 2 → 1 → 3 = 1 + 1 = 2But Dijkstra pops node 1 first (distance 2 is smaller than 5), marks it final, and uses it to set dist[3] = 3. When it later discovers the cheaper route through 2, node 1 is already visited.
Running our dijkstra() function on this directed graph returns:
dist = [0, 2, 5, 3]The correct answer is [0, 1, 5, 2], so Dijkstra gave two wrong distances.
Never use Dijkstra's algorithm when the graph has negative edge weights. Use Bellman-Ford instead, which we study in the next chapter.
Zero-weight edges are fine. Only negative weights cause problems.
Directed and Undirected Graphs
Dijkstra works on both. The only difference is how you build the adjacency list:
Undirected: add u → v AND v → u
Directed: add only u → vOne subtle point: in an undirected graph, a single negative edge u - v already behaves like a negative cycle (you can go back and forth forever), so shortest paths are not even well defined.
Dijkstra on a Grid
Many interview problems hide a graph inside a 2D grid. Each cell is a vertex, and moving to a neighboring cell has a cost.
For example, "minimum cost path where each cell has a cost to enter":
1 3 1
1 5 1
4 2 1If you can move in all four directions, this is just Dijkstra where the priority queue stores {row, col, cost}. The cheapest path from top-left to bottom-right is:
1 → 3 → 1 → 1 → 1 total = 7The pattern is exactly the same: pop the cheapest cell, skip it if already visited, relax its 4 neighbors.
Common Mistakes
1. Using Dijkstra with Negative Weights
As we saw, the answer can silently be wrong. Check the constraints before choosing the algorithm.
2. Integer Overflow
If you compute dist[u] + w while dist[u] is Integer.MAX_VALUE, the result wraps around to a large negative number. In the priority-queue version this cannot happen, because a node is popped only after it has received a real distance. But in other variations, always check dist[u] != INF first. If path sums can exceed about 2.1 billion, use long.
3. Using a Max Heap by Mistake
Java's PriorityQueue is a min heap by default, but if you write a wrong comparator (for example b[1] - a[1]), you get the farthest node first and the algorithm breaks.
4. Forgetting to Skip Stale Entries
Without the visited (or d > dist[u]) check, a node may be processed many times. The answer is still correct for non-negative weights, but the algorithm does a lot of unnecessary extra work.
5. Using BFS for Weighted Graphs
BFS minimizes the number of edges, not the total weight.
6. Marking Visited When Pushing
In BFS, we mark a node visited when we add it to the queue. In Dijkstra, we mark it visited only when we pop it, because a better distance may still be found before then.
Dijkstra vs BFS vs Other Algorithms
Algorithm | Graph type | Negative edges? | Time |
|---|---|---|---|
BFS | Unweighted | Not applicable | O(V + E) |
Dijkstra | Weighted, single source | No | O((V + E) log V) |
Bellman-Ford | Weighted, single source | Yes (detects negative cycles) | O(V · E) |
Floyd-Warshall | Weighted, all pairs | Yes (no negative cycles) | O(V³) |
We cover Bellman-Ford and Floyd-Warshall in the next chapter.
Dijkstra vs Prim
Dijkstra looks very similar to Prim's algorithm from the Minimum Spanning Tree chapter. Both use a min priority queue. The difference is the key stored in the queue:
Prim: key = weight of the single edge connecting v to the tree
Dijkstra: key = total distance from the source to vSo Prim builds the cheapest tree connecting all vertices, while Dijkstra builds the tree of shortest paths from one source. They are usually different trees.
Real-Life Applications
Maps and navigation: shortest route by distance or time (real systems use faster variants such as A* built on the same idea).
Network routing: link-state routing protocols like OSPF use Dijkstra's shortest path first (SPF) algorithm.
Games: finding the cheapest path for a character on a weighted map.
Flight booking: cheapest route between two cities.
Interview Tips and Practice Problems
Look for these signals in a problem:
"minimum cost / minimum time / shortest distance"
+ edges or moves with DIFFERENT non-negative costs
→ DijkstraGood problems to practice:
Network Delay Time (LeetCode 743)
Path With Minimum Effort (LeetCode 1631)
Cheapest Flights Within K Stops (LeetCode 787) – a twist with a limit on stops
Path with Maximum Probability (LeetCode 1514)
Swim in Rising Water (LeetCode 778)
Number of Ways to Arrive at Destination (LeetCode 1976)
The Main Idea
Dijkstra's Algorithm finds the shortest distance from one source to every other vertex in a graph with non-negative edge weights.
The process is:
dist[source] = 0, others = ∞
↓
Pop the closest unvisited vertex
↓
Mark it final (visited)
↓
Relax all its edges
↓
Push improved distances into the priority queue
↓
Repeat until the queue is emptyThe key relationship is:
Dijkstra
↓
Min Priority Queue
↓
Greedy: always expand the closest vertexIts complexity with a binary heap is:
Time → O((V + E) log V)
Space → O(V + E)Remember these four things:
1. Dijkstra uses a min priority queue.
2. Relaxation: if dist[u] + w < dist[v], update dist[v].
3. A vertex is final when it is popped, not when it is pushed.
4. Dijkstra does NOT work with negative edge weights.If a problem asks for the minimum total cost in a graph where costs are different but never negative, Dijkstra should be your first choice.