Dijkstra's Algorithm

Verified Sources

May 19, 2026

Dijkstra's Algorithm solves the single-source shortest path problem: given a weighted graph and a source vertex, it computes the minimum path cost from the source to every reachable vertex, provided all edge weights are nonnegative.2 The algorithm is a classic greedy algorithm because it repeatedly selects the unsettled vertex with the smallest known tentative distance and permanently settles it.2

A useful way to view the method is through relaxation: for each edge $(u,v)$ with weight $w(u,v)$ , we test whether going through $u$ improves the current estimate for $v$ :

\text{dist}[v] \leftarrow \min(\text{dist}[v], \text{dist}[u] + w(u,v)).

This local update rule, combined with the nonnegative-edge assumption, yields globally correct shortest-path distances.2

Dijkstra's algorithm is foundational in route planning, network routing, and many graph-processing systems. For example, it underlies shortest-route computation in transportation networks and is used in routing protocols such as OSPF and IS-IS.

Dijkstra's algorithm - Wikipedia - Overview of the algorithm, applications, and implementation complexity. ↩
Dijkstra Algorithm Explained: Why It Actually Works | Codeintuition - Clear explanation of the greedy invariant and why nonnegative weights are required. ↩ ↩² ↩³
Dijkstra’s Algorithm with a Priority Queue - Practical walkthrough of heap-based implementation and stale-entry handling. ↩
1 Non-negative weights - László Kozma - Lecture notes covering relaxation, invariants, and correctness reasoning. ↩
Dijkstra's algorithm - Wikipedia - Notes on applications including route planning, OSPF, IS-IS, and use as a subroutine. ↩

Dijkstra's algorithm in 3 minutes

Core Applicability Condition

Dijkstra's algorithm is correct only when all edge weights are nonnegative. If negative edges are present, the greedy settlement step can become invalid.2

Dijkstra Algorithm Explained: Why It Actually Works | Codeintuition - Clear explanation of the greedy invariant and why nonnegative weights are required. ↩
Dijkstra's Algorithm - GeeksforGeeks - Explanation of why negative weights invalidate Dijkstra's correctness argument. ↩

Problem setting and intuition

Let $G=(V,E)$ be a weighted graph, directed or undirected. We choose a source vertex $s$ and seek the shortest-path distance $\delta(s,v)$ to each vertex $v \in V$ .2 The algorithm maintains:

a tentative distance array $\text{dist}$
an optional predecessor array $\text{parent}$ for path reconstruction
a min-priority queue keyed by current tentative distance2

Initially,

\text{dist}[s]=0, \qquad \text{dist}[v]=\infty \text{ for } v\neq s.

At each iteration, the minimum-distance unsettled vertex is extracted. Because all remaining edges are nonnegative, no future path can improve that extracted value; therefore the distance becomes final.2

This is the central invariant:

Invariant	Meaning	Why it matters
Tentative distances are upper bounds	$\text{dist}[v] \ge \delta(s,v)$ never becomes too small	Prevents invalid underestimation
Extracted minimum is final	Once vertex $u$ is removed from the queue, $\text{dist}[u]=\delta(s,u)$	Gives correctness of the greedy choice2
Relaxation propagates improvements	Better paths discovered through settled vertices update neighbors	Builds shortest paths incrementally2

The algorithm may stop early if only a single target is needed: once that target is extracted from the queue, its shortest distance is known.

Dijkstra's algorithm - Wikipedia - Overview of the algorithm, applications, and implementation complexity. ↩ ↩²
1 Non-negative weights - László Kozma - Lecture notes covering relaxation, invariants, and correctness reasoning. ↩ ↩² ↩³
Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8 - GeeksforGeeks - Complexity discussion for adjacency lists, binary heaps, and Fibonacci heaps. ↩ ↩²
Dijkstra Algorithm Explained: Why It Actually Works | Codeintuition - Clear explanation of the greedy invariant and why nonnegative weights are required. ↩ ↩² ↩³
Dijkstra's Algorithm - GeeksforGeeks - Explanation of why negative weights invalidate Dijkstra's correctness argument. ↩
Dijkstra's algorithm - Wikipedia - Notes on applications including route planning, OSPF, IS-IS, and use as a subroutine. ↩

How Dijkstra's Algorithm Executes

1
Step 1
Set the source distance to 0 and every other vertex to ∞. Initialize a predecessor array if path reconstruction is required.2

Footnotes

Dijkstra's algorithm - Wikipedia - Overview of the algorithm, applications, and implementation complexity. ↩

Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8 - GeeksforGeeks - Complexity discussion for adjacency lists, binary heaps, and Fibonacci heaps. ↩
2
Step 2
Store vertices keyed by their current tentative distances. In practical implementations, a binary heap is common because it supports efficient extract-min and update operations.2

Footnotes

Dijkstra's algorithm - Wikipedia - Overview of the algorithm, applications, and implementation complexity. ↩

Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8 - GeeksforGeeks - Complexity discussion for adjacency lists, binary heaps, and Fibonacci heaps. ↩
3
Step 3
Remove the unsettled vertex with minimum tentative distance. This vertex is now considered settled, meaning its shortest-path distance is final under the nonnegative-weight assumption.2

Footnotes

Dijkstra Algorithm Explained: Why It Actually Works | Codeintuition - Clear explanation of the greedy invariant and why nonnegative weights are required. ↩

Dijkstra's Algorithm - GeeksforGeeks - Explanation of why negative weights invalidate Dijkstra's correctness argument. ↩
4
Step 4
For every edge from the extracted vertex to a neighbor, test whether the path through the extracted vertex is shorter. If so, update the neighbor's distance and predecessor, then adjust its priority in the queue.2

Footnotes

Dijkstra Algorithm Explained: Why It Actually Works | Codeintuition - Clear explanation of the greedy invariant and why nonnegative weights are required. ↩

1 Non-negative weights - László Kozma - Lecture notes covering relaxation, invariants, and correctness reasoning. ↩
5
Step 5
Continue until the queue is empty, or terminate earlier if a specific destination has just been extracted. At that point, all settled vertices have correct shortest distances.2

Footnotes

Dijkstra's algorithm - Wikipedia - Notes on applications including route planning, OSPF, IS-IS, and use as a subroutine. ↩

Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8 - GeeksforGeeks - Complexity discussion for adjacency lists, binary heaps, and Fibonacci heaps. ↩

Worked example

Consider the weighted graph below with source $A$ .

Initialization gives:

$\text{dist}[A]=0$
$\text{dist}[B]=\infty$
$\text{dist}[C]=\infty$
$\text{dist}[D]=\infty$
$\text{dist}[E]=\infty$

After relaxing edges from $A$ , we get:

$\text{dist}[B]=4$
$\text{dist}[C]=1$

Next, $C$ is extracted because it has the smallest tentative distance. Relaxing from $C$ improves $B$ from $4$ to $3$ , and sets $D$ to $6$ .2 Then $B$ is extracted with distance $3$ , which improves $D$ to $4$ . Finally, $D$ improves $E$ to $7$ .

Final shortest distances from $A$ are:

Vertex	Shortest distance from $A$	One shortest path
A	0	A
B	3	A → C → B
C	1	A → C
D	4	A → C → B → D
E	7	A → C → B → D → E

This example illustrates why repeated relaxation plus greedy extraction is effective: the shortest-path tree emerges incrementally as better paths are discovered and finalized.2

Dijkstra’s Algorithm with a Priority Queue - Practical walkthrough of heap-based implementation and stale-entry handling. ↩ ↩² ↩³
Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8 - GeeksforGeeks - Complexity discussion for adjacency lists, binary heaps, and Fibonacci heaps. ↩
Dijkstra Algorithm Explained: Why It Actually Works | Codeintuition - Clear explanation of the greedy invariant and why nonnegative weights are required. ↩

Why Negative Edges Break the Algorithm

If a vertex is settled too early, a later path that includes a negative edge could reduce its distance. That contradicts Dijkstra's key invariant that extracted distances are final.2

Dijkstra Algorithm Explained: Why It Actually Works | Codeintuition - Clear explanation of the greedy invariant and why nonnegative weights are required. ↩
Dijkstra's Algorithm - GeeksforGeeks - Explanation of why negative weights invalidate Dijkstra's correctness argument. ↩

Correctness: why the greedy choice works

The correctness argument depends on a simple but powerful property. Suppose vertex $u$ is the unsettled vertex with smallest tentative distance. If all edge weights are nonnegative, then any alternative path to $u$ through another unsettled vertex must have length at least $\text{dist}[u]$ plus some nonnegative amount, so it cannot be shorter.2 Hence:

\text{when } u \text{ is extracted, } \text{dist}[u] = \delta(s,u).

This proof is often expressed as a loop invariant or induction argument. The two central claims are:

Tentative distances never underestimate true shortest distances.
Each extracted vertex has the correct final distance.2

Once claim 2 holds for the current extraction, relaxing outgoing edges preserves claim 1 and allows the frontier of known shortest paths to expand safely.

A concise conceptual summary is:

Dijkstra Algorithm Explained: Why It Actually Works | Codeintuition - Clear explanation of the greedy invariant and why nonnegative weights are required. ↩ ↩² ↩³
1 Non-negative weights - László Kozma - Lecture notes covering relaxation, invariants, and correctness reasoning. ↩ ↩² ↩³ ↩⁴

1import heapq
2
3
4def dijkstra(graph, source):
5    dist = {v: float('inf') for v in graph}
6    parent = {v: None for v in graph}
7    dist[source] = 0
8    pq = [(0, source)]
9
10    while pq:
11        curr_dist, u = heapq.heappop(pq)
12
13        if curr_dist != dist[u]:
14            continue
15
16        for v, w in graph[u]:
17            new_dist = curr_dist + w
18            if new_dist < dist[v]:
19                dist[v] = new_dist
20                parent[v] = u
21                heapq.heappush(pq, (new_dist, v))
22
23    return dist, parent

Data structures and complexity

The efficiency of Dijkstra's algorithm depends strongly on the graph representation and priority-queue implementation.3

With an adjacency list and a binary heap, the time complexity is typically $O((V+E)\log V)$ , often written as $O(E\log V)$ for connected sparse graphs.3
With an adjacency matrix and linear scanning for the next minimum, the complexity is $O(V^2)$ .2
With a Fibonacci heap, the theoretical bound can improve to $O(E + V\log V)$ , though binary heaps are often preferred in practice because of simpler implementation and lower constants.

Space usage is usually $O(V+E)$ when the graph is stored as an adjacency list, plus storage for distances, predecessors, and queue state.2

For sparse graphs, adjacency-list implementations are generally much more practical than matrix-based versions.2

Dijkstra's algorithm - Wikipedia - Overview of the algorithm, applications, and implementation complexity. ↩ ↩² ↩³
Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8 - GeeksforGeeks - Complexity discussion for adjacency lists, binary heaps, and Fibonacci heaps. ↩ ↩² ↩³ ↩⁴ ↩⁵
A Complete Guide to Dijkstra's Shortest Path Algorithm | Codecademy - Summary of time and space complexity under common graph representations. ↩ ↩² ↩³ ↩⁴
Dijkstra’s Algorithm with a Priority Queue - Practical walkthrough of heap-based implementation and stale-entry handling. ↩

Typical Time Complexity by Implementation

Relative asymptotic cost of common Dijkstra implementations.3

Dijkstra's algorithm - Wikipedia - Overview of the algorithm, applications, and implementation complexity. ↩
Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8 - GeeksforGeeks - Complexity discussion for adjacency lists, binary heaps, and Fibonacci heaps. ↩
A Complete Guide to Dijkstra's Shortest Path Algorithm | Codecademy - Summary of time and space complexity under common graph representations. ↩

Common Questions and Edge Cases

Practical applications and limitations

Dijkstra's algorithm appears in many real systems because shortest-path computation is a fundamental abstraction for optimization over networks.

Major application areas

Application area	Graph interpretation	Optimization goal
Road navigation	Intersections as vertices, roads as weighted edges	Shortest or fastest route
Network routing	Routers as vertices, links as weighted edges	Lowest-cost forwarding path
Infrastructure planning	Facilities and connections as weighted graph components	Least-cost connectivity analysis
Algorithm design	Subroutine inside larger methods such as Johnson's algorithm	Repeated shortest-path computation

However, Dijkstra has important limitations:

It does not support negative-weight edges safely.2
On very large graphs, naïve implementations can be too slow.2
It computes shortest paths from one source; it is not itself an all-pairs shortest-path algorithm.2

In practice, the algorithm remains one of the most important building blocks in graph theory, routing protocols, and pathfinding because of its strong correctness guarantee and efficient performance on nonnegative weighted graphs.2

Dijkstra's algorithm - Wikipedia - Notes on applications including route planning, OSPF, IS-IS, and use as a subroutine. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷
Dijkstra Algorithm Explained: Why It Actually Works | Codeintuition - Clear explanation of the greedy invariant and why nonnegative weights are required. ↩ ↩²
Dijkstra's Algorithm - GeeksforGeeks - Explanation of why negative weights invalidate Dijkstra's correctness argument. ↩
Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8 - GeeksforGeeks - Complexity discussion for adjacency lists, binary heaps, and Fibonacci heaps. ↩
A Complete Guide to Dijkstra's Shortest Path Algorithm | Codecademy - Summary of time and space complexity under common graph representations. ↩
Dijkstra's algorithm - Wikipedia - Overview of the algorithm, applications, and implementation complexity. ↩

Implementation Best Practice

In heap-based implementations, use a stale-entry check such as if popped_distance != dist[u]: continue to ignore outdated queue entries after a shorter path has already been found.

Dijkstra’s Algorithm with a Priority Queue - Practical walkthrough of heap-based implementation and stale-entry handling. ↩

Knowledge Check

Question 1 of 4

Q1Single choice

What problem does Dijkstra's algorithm solve?

Single-source shortest paths in graphs with nonnegative edge weights

All-pairs shortest paths in graphs with arbitrary weights

Minimum spanning tree for directed graphs

Cycle detection in unweighted graphs

Explore Related Topics

The Banker's Algorithm: Deadlock Avoidance in Operating Systems

The Banker's Algorithm is a deadlock‑avoidance method that keeps a system in a safe state by checking each resource request against the maximum declared needs of processes.

Maintains Available, Max, Allocation, and Need matrices, where $\text{Need}[i][j]=\text{Max}[i][j]-\text{Allocation}[i][j]$ .
The Safety Algorithm uses vectors Work and Finish to find an execution order; if all processes finish, the state is safe.
The Resource‑Request Algorithm simulates allocation, runs the safety check, and commits only if the resulting state remains safe.
Time complexity of the safety check is $O(m \times n^{2})$ .
In practice the algorithm is rarely used because processes must predeclare maximum needs and the algorithm’s overhead is high.

Graph Traversals: Breadth-First Search (BFS) vs. Depth-First Search (DFS)

This content contrasts Breadth‑First Search (BFS) and Depth‑First Search (DFS), outlining their traversal order, complexity, and typical use cases.

BFS uses a FIFO queue, visits nodes level by level (A→B→C→D→E→F); DFS uses a LIFO stack, dives deep (A→B→D→E→C→F).
Both run in $O(V+E)$ time; BFS may need $O(V)$ (or $O(b^d)$ ) space, while DFS typically uses $O(d)$ stack depth.
BFS guarantees the shortest path in unweighted graphs, suited for routing, web crawling, and level‑order serialization.
DFS excels in memory‑limited, wide graphs and in tasks like topological sort and cycle detection, but deep recursion can cause stack overflow.

Minimum Spanning Tree (MST) and Prim's Algorithm

Prim's algorithm builds a minimum spanning tree (MST) of a connected weighted undirected graph by repeatedly adding the cheapest edge that links the current tree to a new vertex.

An MST includes all $V$ vertices, has exactly $V-1$ edges, contains no cycles, and minimizes total edge weight.
The cut property guarantees that the lightest edge crossing any cut (the current tree vs. the rest) is safe to include in an MST.
Algorithm steps: start at any vertex, repeatedly select the minimum‑weight crossing edge, add its outside vertex, and update candidate edges until all vertices are reached.
With an adjacency list and a priority queue, the runtime is $O(E \log V)$ ; using an adjacency matrix it is $O(V^2)$ .
In the example graph, Prim selects edges $AB(2), BC(1), BD(4), CE(6)$ , producing an MST of total weight $13$ .

Research more with Coursify

Dijkstra's Algorithm

AI Summary

Footnotes

Dijkstra's algorithm in 3 minutes

Core Applicability Condition

Footnotes

Problem setting and intuition

Footnotes

How Dijkstra's Algorithm Executes

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Worked example

Footnotes

Why Negative Edges Break the Algorithm

Footnotes

Correctness: why the greedy choice works

Footnotes

Data structures and complexity

Footnotes

Typical Time Complexity by Implementation

Footnotes

Common Questions and Edge Cases

Practical applications and limitations

Major application areas

Footnotes

Implementation Best Practice

Footnotes

Knowledge Check

Explore Related Topics