Dijkstra's Algorithm
Last updated
Dijkstra's algorithm finds the shortest path from a source node to every other node in a graph with non-negative edge weights. It keeps a tentative distance for each node, repeatedly settles the unsettled node with the smallest tentative distance, and relaxes its edges - updating a neighbor's distance whenever a shorter route through the current node is found. Press play above to watch distances drop as each node is settled.
The key insight is greedy: once the nearest unsettled node is picked, its distance is final, because all other routes to it would have to pass through a node that is already farther away. With a binary-heap priority queue, Dijkstra runs in O((V + E) log V) time. It requires non-negative weights - use Bellman-Ford if edges can be negative.
Time & space complexity
| Implementation | Complexity | Notes |
|---|---|---|
| Binary heap | O((V + E) log V) | The common, practical choice |
| Array scan | O(V²) | Simpler; fine for dense graphs |
| Space | O(V) | Distances + priority queue |
| Requires | Non-negative weights | Negative edges break the greedy choice |
Step by step
| Step | What happens |
|---|---|
| 1 | Set the source distance to 0 and all others to infinity. |
| 2 | Pick the unsettled node with the smallest tentative distance. |
| 3 | Mark it settled - its shortest distance is now final. |
| 4 | For each neighbor, compute distance-through-current + edge weight. |
| 5 | If that is smaller than the neighbor's current distance, relax it. |
| 6 | Repeat until all reachable nodes are settled. |
Worked example
Shortest paths from source A on the graph with edges A-B=4, A-C=1, C-B=2, C-D=5, B-D=1:
| Step | Settle | Distances | Action |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Initialize: source A=0, all others infinity. |
| 1 | A (0) | B=4, C=1, D=∞ | Relax edges from A: set B=4, C=1. |
| 2 | C (1) | B=3, D=6 | Through C: B=1+2=3 beats 4; D=1+5=6. |
| 3 | B (3) | D=4 | Through B: D=3+1=4 beats 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Settle D; nothing left to relax. Done. |
When to use Dijkstra's algorithm
| Use it when | Avoid it when |
|---|---|
| All edge weights are non-negative | Any edge can be negative - use Bellman-Ford |
| You need shortest paths from one source to all nodes | You need all-pairs shortest paths - Floyd-Warshall is simpler |
| The graph is weighted and you want exact distances | The graph is unweighted - plain BFS is faster and simpler |
| You have a good heap/priority-queue available | You want to reach a single target fast with a heuristic - use A* |
Dijkstra's Algorithm code
A clean, runnable Dijkstra's Algorithm implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Dijkstra's Algorithm code in Python
Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")Dijkstra's Algorithm code in JavaScript
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));Dijkstra's Algorithm code in Java
Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}Dijkstra's Algorithm code in C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}Dijkstra's Algorithm code in C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}Dijkstra's Algorithm FAQ
What is the time complexity of Dijkstra's algorithm?
With a binary-heap priority queue it runs in
O((V + E) log V). A simple version that scans an array for the minimum each step is O(V²), which can actually be faster on dense graphs. Both use O(V) space.Why doesn't Dijkstra work with negative edge weights?
Dijkstra assumes that once it settles the closest unsettled node, that distance is final. A negative edge could later create a shorter path to an already-settled node, breaking that assumption. For graphs with negative weights, use the Bellman-Ford algorithm.
What is the difference between Dijkstra and BFS?
BFS finds shortest paths counting edges (each edge weight is effectively 1), using a plain queue. Dijkstra generalizes this to weighted graphs by always expanding the node with the smallest total distance, using a priority queue. On an unweighted graph the two produce the same paths.
What is the difference between Dijkstra and A* search?
A* is Dijkstra plus a heuristic that estimates the remaining distance to a target, so it steers the search toward that goal instead of expanding uniformly in all directions. When the heuristic is zero, A* degenerates into exactly Dijkstra. Use A* when you have a single destination and a good admissible heuristic; use Dijkstra when you need distances to every node.
When should I use Dijkstra instead of Bellman-Ford?
Use Dijkstra whenever all edge weights are non-negative - it is faster at
O((V + E) log V) versus Bellman-Ford's O(V·E). Choose Bellman-Ford only when edges can be negative or you need to detect negative cycles. On non-negative graphs Dijkstra is almost always the better choice.Can Dijkstra revisit a node after it has been settled?
No - once a node is settled, its distance is final and it is never relaxed again. A common gotcha in heap implementations is leaving stale entries in the priority queue after a node's distance improves; you must skip a popped node if it is already settled (its popped distance exceeds its recorded distance). Forgetting this check still yields correct answers but wastes work.
Related resources
More visualizations
