Free explainer · Video · Code · Quiz
Dijkstra's Algorithm
Shortest paths from one starting point in a weighted graph: always finish the closest unfinished vertex next, using a priority queue. Distances, path reconstruction, and why negative edges break it.
- Difficulty
- Medium
- Time
- O((V + E) log V)
- Space
- O(V + E)
Try it yourself
Step through it at your own pace — this is Pathfinding Maze, running right on the page.
LivePathfinding Maze
Loading the preview…
How it works
The idea, a worked example, and the traps to avoid.
The idea
Pour water into one corner of a network of pipes, where each pipe takes a certain number of seconds to cross. The water spreads out at the same speed everywhere, and the moment it first reaches a junction is exactly the shortest travel time to that junction. If some other route were faster, the water flowing along it would have got there first.
Dijkstra's algorithm simulates that spreading. It keeps a tentative distance for every vertex and repeatedly finishes the closest vertex not finished yet. A priority queue hands us that vertex quickly. When a vertex is finished, we check its outgoing edges and see whether going through it gives a neighbour a shorter route. That check is called relaxing an edge.
Walkthrough
An undirected graph with edges A–B (4), A–C (1), C–B (2), B–D (1), C–D (5), D–E (3). Start at A. Every distance starts at ∞, except A at 0.
| Step | Pop | What happens | Queue afterwards |
|---|---|---|---|
| 1 | (0, A) | A→B: B = 4. A→C: C = 1 | (1, C), (4, B) |
| 2 | (1, C) | C→B: 1 + 2 = 3 < 4, so B = 3 via C. C→D: D = 6 | (3, B), (4, B), (6, D) |
| 3 | (3, B) | B→D: 3 + 1 = 4 < 6, so D = 4 via B | (4, B), (4, D), (6, D) |
| 4 | (4, B) | Stale: B is already 3. Skip it | (4, D), (6, D) |
| 5 | (4, D) | D→E: E = 7 | (6, D), (7, E) |
| 6 | (6, D) | Stale: D is already 4. Skip it | (7, E) |
| 7 | (7, E) | Nothing improves | empty |
Final distances: A 0, C 1, B 3, D 4, E 7. Notice step 2. The direct edge A→B costs 4, but the detour through C costs only 3. Dijkstra found it because it finished C (distance 1) before B.
Rebuilding the path. Every time a distance improves, we record where it came from in prev. To get to E, walk backwards: E came from D, D from B, B from C, C from A. Reverse that and the path is A → C → B → D → E. If the walk never reaches the source, the target is unreachable and shortestPath returns an empty path.
Lazy deletion
Look at steps 4 and 6. When B improved from 4 to 3, the old entry (4, B) stayed in the queue. The textbook version uses a "decrease-key" operation to update it in place, but the heaps in most standard libraries (heapq, Java's PriorityQueue, C++'s priority_queue) can't do that. So we push a fresh entry and ignore the outdated ones when they come out: if the popped distance is bigger than dist[u], skip it. Simple, and just as fast in practice.
Why it's correct
Claim: when a vertex u comes out of the queue with its current distance, that distance is final.
Suppose some shorter route to u existed. It starts inside the set of finished vertices, so at some point it crosses an edge x → y from a finished vertex x to an unfinished vertex y. When x was finished, that edge was relaxed, so y already sits in the queue with a distance no bigger than the route's length up to y. Edges can't be negative, so the rest of the route only adds length: y's entry is at most the whole route, which is shorter than u's distance. The queue would have handed us y first. Contradiction.
The key step is "the rest of the route only adds length". That's the one place the proof needs non-negative weights.
Why negative edges break it
Take A→B (2), A→C (3), C→B (−2). Dijkstra finishes B at distance 2, but A → C → B costs 1. Once B is finished it's never revisited, so the answer is wrong.
With negative edges, use Bellman-Ford. It's O(V·E), slower, but it handles negative weights and also detects negative cycles, where "shortest path" stops making sense. Adding a constant to every edge to make them positive does not work. It penalises paths with more edges and changes which path is shortest.
Complexity
Each vertex is finished once, and each edge is relaxed at most once, when its start vertex is finished. That's at most E pushes and E pops, each costing O(log E) = O(log V), because E ≤ V². Total: O((V + E) log V) time, and O(V + E) space for the graph, the distance and prev arrays, and the queue.
On very dense graphs, a version that scans an array for the minimum instead of using a heap runs in O(V²), which is better there.
Common bugs
- Marking a vertex done when you push it, instead of when you pop it. Its distance can still improve, so the answers come out wrong.
- Forgetting the stale check. The answers stay correct, but you redo work for every outdated entry.
- Overflow. Sums of int weights can pass 2³¹. Use
longorlong longfor distances, and never add to "infinity". - Undirected graphs. Add each edge in both directions.
- Using BFS on weighted graphs. BFS is only right when every edge has the same weight.
When to use it (and when not)
Use it for shortest paths from one source with non-negative weights: road maps, network routing (OSPF is Dijkstra), game maps, grids with movement costs. If you only need one target, you can stop as soon as it's popped.
Use something else for negative weights (Bellman-Ford), unweighted graphs (plain BFS, O(V + E)), all pairs on a small dense graph (Floyd-Warshall), or one target with a good distance estimate (A*, which is Dijkstra plus a heuristic).
Interview variations
- Network delay time. Run Dijkstra from the source. The answer is the largest distance, or −1 if any vertex is unreachable.
- Cheapest path on a grid ("path with minimum effort", "swim in rising water"). The cells are the vertices and the four neighbours are the edges. You don't need to build the graph; generate neighbours on the fly.
- Cheapest flights within K stops. The plain algorithm ignores the stop limit. Make the state
(city, stops used), or run Bellman-Ford for K + 1 rounds.
Code
The same algorithm, step for step, in 4 languages.
// Dijkstra's algorithm: shortest distances from one source in a graph whose edge weights are all >= 0.
// A priority queue always hands us the closest vertex we have not finished yet — and with no
// negative edges, nothing found later can beat that distance, so it is final.
/** @typedef {[to: number, weight: number]} Edge an edge to `to`, with weight >= 0 */
/**
* The priority queue: a binary min-heap of [distance, vertex] pairs, stored in an array where
* the children of index i live at 2i + 1 and 2i + 2. Ties on distance go to the smaller vertex,
* so the result never depends on the order entries happened to arrive in.
*/
class MinHeap {
/** @type {Array<[number, number]>} */
#items = [];
get size() {
return this.#items.length;
}
/** @param {[number, number]} item */
push(item) {
this.#items.push(item);
this.#siftUp(this.#items.length - 1);
}
/** Removes and returns the smallest pair. Call only when size > 0. */
pop() {
const items = this.#items;
const top = items[0];
const last = items.pop();
if (items.length > 0) {
items[0] = last; // move the last leaf to the root, then let it sink to its place
this.#siftDown(0);
}
return top;
}
/** @param {number} child */
#siftUp(child) {
while (child > 0) {
const parent = (child - 1) >> 1;
if (!isLess(this.#items[child], this.#items[parent])) return;
this.#swap(child, parent);
child = parent;
}
}
/** @param {number} parent */
#siftDown(parent) {
while (true) {
const smallest = this.#smallestOf(parent);
if (smallest === parent) return;
this.#swap(parent, smallest);
parent = smallest;
}
}
/**
* The index of the smallest pair among `index` and its (up to two) children.
* @param {number} index
*/
#smallestOf(index) {
let smallest = index;
for (const child of [2 * index + 1, 2 * index + 2]) {
if (child < this.#items.length && isLess(this.#items[child], this.#items[smallest])) smallest = child;
}
return smallest;
}
/**
* @param {number} a
* @param {number} b
*/
#swap(a, b) {
[this.#items[a], this.#items[b]] = [this.#items[b], this.#items[a]];
}
}
/**
* Orders [distance, vertex] pairs by distance, then by vertex.
* @param {[number, number]} a
* @param {[number, number]} b
*/
function isLess(a, b) {
if (a[0] !== b[0]) return a[0] < b[0];
return a[1] < b[1];
}
/**
* Shortest distances from `source` to every vertex.
*
* @param {Edge[][]} graph adjacency list: graph[u] lists the edges leaving vertex u
* @param {number} source the start vertex, 0 <= source < graph.length
* @returns {{ dist: number[], prev: number[] }}
* dist[v]: length of the shortest path source → v (Infinity when v cannot be reached);
* prev[v]: the vertex just before v on that path (-1 for the source and unreachable vertices)
*/
export function dijkstra(graph, source) {
const dist = new Array(graph.length).fill(Infinity);
const prev = new Array(graph.length).fill(-1);
const queue = new MinHeap();
dist[source] = 0;
queue.push([0, source]);
while (queue.size > 0) {
const [distance, u] = queue.pop();
// Lazy deletion: u may sit in the queue several times. Only its best entry counts.
if (distance > dist[u]) continue;
for (const [v, weight] of graph[u]) {
const candidate = distance + weight;
if (candidate < dist[v]) {
// Relax the edge u → v: going through u is shorter than anything seen so far.
dist[v] = candidate;
prev[v] = u;
queue.push([candidate, v]);
}
}
}
return { dist, prev };
}
/**
* Rebuilds the shortest path source → target by walking `prev` backwards from the target.
*
* @param {number[]} prev the `prev` array returned by `dijkstra`
* @param {number} source the source `dijkstra` ran from
* @param {number} target where the path should end
* @returns {number[]} the vertices from source to target, or [] if target cannot be reached
*/
export function shortestPath(prev, source, target) {
const path = [];
for (let v = target; v !== -1; v = prev[v]) path.push(v);
path.reverse();
return path[0] === source ? path : [];
}
# Dijkstra's algorithm: shortest distances from one source in a graph whose edge weights are all >= 0.
# A priority queue always hands us the closest vertex we have not finished yet — and with no
# negative edges, nothing found later can beat that distance, so it is final.
import heapq
import math
from typing import List, Tuple
# Adjacency list: graph[u] lists the edges leaving u as (to, weight) pairs, weight >= 0.
Graph = List[List[Tuple[int, int]]]
def dijkstra(graph: Graph, source: int) -> Tuple[List[float], List[int]]:
"""Return (dist, prev) for every vertex.
dist[v]: length of the shortest path source -> v (math.inf when v cannot be reached).
prev[v]: the vertex just before v on that path (-1 for the source and unreachable vertices).
"""
dist: List[float] = [math.inf] * len(graph)
prev = [-1] * len(graph)
dist[source] = 0
# heapq keeps the smallest (distance, vertex) tuple first; ties go to the smaller vertex.
queue: List[Tuple[float, int]] = [(0, source)]
while queue:
distance, u = heapq.heappop(queue)
# Lazy deletion: u may sit in the queue several times. Only its best entry counts.
if distance > dist[u]:
continue
for v, weight in graph[u]:
candidate = distance + weight
if candidate < dist[v]:
# Relax the edge u -> v: going through u is shorter than anything seen so far.
dist[v] = candidate
prev[v] = u
heapq.heappush(queue, (candidate, v))
return dist, prev
def shortest_path(prev: List[int], source: int, target: int) -> List[int]:
"""Rebuild the path source -> target by walking prev backwards from the target.
Return the vertices from source to target, or [] if target cannot be reached.
"""
path = []
v = target
while v != -1:
path.append(v)
v = prev[v]
path.reverse()
return path if path[0] == source else []
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
/**
* Dijkstra's algorithm: shortest distances from one source in a graph whose edge weights are all >= 0.
* A priority queue always hands us the closest vertex we have not finished yet — and with no
* negative edges, nothing found later can beat that distance, so it is final.
*/
public final class Dijkstra {
/** dist[v] for a vertex the source cannot reach. */
public static final long UNREACHABLE = Long.MAX_VALUE;
/** An edge to vertex {@code to}, with weight >= 0. The graph is a list of these per vertex. */
public record Edge(int to, int weight) {
}
/**
* dist[v]: length of the shortest path source → v ({@link #UNREACHABLE} when there is none).
* prev[v]: the vertex just before v on that path (-1 for the source and unreachable vertices).
*/
public record Result(long[] dist, int[] prev) {
}
/** A queue entry. Ties on distance go to the smaller vertex, so the result is deterministic. */
private record Entry(long dist, int vertex) {
}
private static final Comparator<Entry> CLOSEST_FIRST =
Comparator.comparingLong(Entry::dist).thenComparingInt(Entry::vertex);
private Dijkstra() {
}
/** Shortest distances from source to every vertex of graph (an adjacency list). */
public static Result dijkstra(List<List<Edge>> graph, int source) {
long[] dist = new long[graph.size()];
int[] prev = new int[graph.size()];
Arrays.fill(dist, UNREACHABLE);
Arrays.fill(prev, -1);
PriorityQueue<Entry> queue = new PriorityQueue<>(CLOSEST_FIRST);
dist[source] = 0;
queue.add(new Entry(0, source));
while (!queue.isEmpty()) {
Entry entry = queue.poll();
int u = entry.vertex();
// Lazy deletion: u may sit in the queue several times. Only its best entry counts.
if (entry.dist() > dist[u]) {
continue;
}
for (Edge edge : graph.get(u)) {
long candidate = entry.dist() + edge.weight(); // long: sums of ints can overflow int
if (candidate < dist[edge.to()]) {
// Relax the edge u → v: going through u is shorter than anything seen so far.
dist[edge.to()] = candidate;
prev[edge.to()] = u;
queue.add(new Entry(candidate, edge.to()));
}
}
}
return new Result(dist, prev);
}
/**
* Rebuilds the path source → target by walking prev backwards from the target.
* Returns the vertices from source to target, or an empty list if target cannot be reached.
*/
public static List<Integer> shortestPath(int[] prev, int source, int target) {
List<Integer> path = new ArrayList<>();
for (int v = target; v != -1; v = prev[v]) {
path.add(v);
}
Collections.reverse(path);
return path.get(0) == source ? path : List.of();
}
}
// Dijkstra's algorithm: shortest distances from one source in a graph whose edge weights are all >= 0.
// A priority queue always hands us the closest vertex we have not finished yet — and with no
// negative edges, nothing found later can beat that distance, so it is final.
#include <algorithm>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
// An edge to vertex `to`, with weight >= 0.
struct Edge {
int to;
int weight;
};
// Adjacency list: graph[u] lists the edges leaving vertex u.
using Graph = std::vector<std::vector<Edge>>;
// dist[v] for a vertex the source cannot reach.
constexpr long long UNREACHABLE = std::numeric_limits<long long>::max();
// dist[v]: length of the shortest path source -> v (UNREACHABLE when there is none).
// prev[v]: the vertex just before v on that path (-1 for the source and unreachable vertices).
struct ShortestPaths {
std::vector<long long> dist;
std::vector<int> prev;
};
ShortestPaths dijkstra(const Graph& graph, int source) {
ShortestPaths result{std::vector<long long>(graph.size(), UNREACHABLE), std::vector<int>(graph.size(), -1)};
std::vector<long long>& dist = result.dist;
std::vector<int>& prev = result.prev;
// (distance, vertex) pairs; std::greater turns the max-heap into a min-heap.
// Ties on distance go to the smaller vertex, so the result is deterministic.
using Entry = std::pair<long long, int>;
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> queue;
dist[source] = 0;
queue.push({0, source});
while (!queue.empty()) {
auto [distance, u] = queue.top();
queue.pop();
// Lazy deletion: u may sit in the queue several times. Only its best entry counts.
if (distance > dist[u]) {
continue;
}
for (const Edge& edge : graph[u]) {
long long candidate = distance + edge.weight; // long long: sums of ints can overflow int
if (candidate < dist[edge.to]) {
// Relax the edge u -> v: going through u is shorter than anything seen so far.
dist[edge.to] = candidate;
prev[edge.to] = u;
queue.push({candidate, edge.to});
}
}
}
return result;
}
// Rebuilds the path source -> target by walking prev backwards from the target.
// Returns the vertices from source to target, or an empty vector if target cannot be reached.
std::vector<int> shortestPath(const std::vector<int>& prev, int source, int target) {
std::vector<int> path;
for (int v = target; v != -1; v = prev[v]) {
path.push_back(v);
}
std::reverse(path.begin(), path.end());
if (path.front() != source) {
return {};
}
return path;
}
Ask about this algorithm
Stuck on a step? Ask for another example or why it works.
Test yourself
10 quick questions to check it stuck.
Q1 · A directed graph with 6 vertices and these edges (from → to, weight): 0→1 (7), 0→2 (2), 2→1 (3), 1→3 (1), 2→3 (8), 3→4 (2), 2→4 (9). Vertex 5 has no edges. After dijkstra(graph, 0), what is dist[4] and which path does shortestPath give for target 4?
Take it further
- Animation
Pathfinding Maze
An editable neon maze where BFS, Dijkstra, A* and greedy search race to the goal, step by step
Free
