•
•
•
•
•
•
•
Learn how Dijkstra’s algorithm works on non-negative weighted graphs, with a worked example, implementation guidance and common mistakes.
Dijkstra’s algorithm computes shortest-path distances from one starting vertex to other reachable vertices in a weighted graph, provided edge weights are non-negative. It is used in routing, network analysis, maps and many graph problems.
A reliable explanation should distinguish the algorithm’s established guarantee from claims about newer research: Dijkstra’s algorithm itself is a classic method, not a new 2025 invention.
| Property | Detail |
|---|---|
| Problem | Single-source shortest paths |
| Graph | Directed or undirected, weighted |
| Edge-weight requirement | Non-negative weights |
| Typical efficient implementation | Adjacency list plus min-priority queue |
| Common complexity | (O((V+E)\log V)) with a binary heap, often simplified to (O(E\log V)) for connected sparse graphs |
| Not suitable as-is for | Graphs with negative-weight edges |
Here, (V) is the number of vertices and (E) is the number of edges.
The algorithm keeps a tentative distance from the source to every vertex. Initially, the source distance is zero and all other distances are infinity. Repeatedly select the unsettled vertex with the smallest tentative distance, then try to improve the distances of its neighbours.
This improvement step is called relaxation. For an edge from (u) to (v) with weight (w), compare the current distance to (v) with the distance to (u) plus (w):
[
d[v] \leftarrow \min(d[v], d[u] + w)
]
When all weights are non-negative, the smallest unsettled distance is final when selected, which is the key property behind Dijkstra’s correctness.
Consider these undirected weighted edges:
| Edge | Weight |
|---|---|
| A–B | 4 |
| A–C | 1 |
| C–B | 2 |
| B–D | 1 |
| C–D | 5 |
Find shortest distances from A.
| Vertex | Shortest distance from A | One shortest path |
|---|---|---|
| A | 0 | A |
| C | 1 | A → C |
| B | 3 | A → C → B |
| D | 4 | A → C → B → D |
The algorithm stores predecessors as distances improve. Following those predecessors backwards reconstructs a path.
function dijkstra(graph, source):
for each vertex v:
dist[v] = infinity
previous[v] = undefined
dist[source] = 0
priority_queue.push((0, source))
while priority_queue is not empty:
(distance, u) = priority_queue.pop_min()
if distance != dist[u]:
continue // ignore an outdated queue entry
for each edge (u, v, weight) in graph[u]:
candidate = dist[u] + weight
if candidate < dist[v]:
dist[v] = candidate
previous[v] = u
priority_queue.push((candidate, v))
return dist, previousThe outdated-entry check is useful when the priority queue does not support decrease-key directly. The pseudocode assumes all edge weights are non-negative.
With an adjacency list and binary heap, the usual time bound is (O((V+E)\log V)), and graph plus auxiliary storage is (O(V+E)). An implementation using a simple array to select the next vertex can take (O(V^2)), which may be reasonable for dense graphs or small inputs.
Complexity depends on the data structures and graph representation. State which implementation is being analysed rather than presenting one bound as universal.
A negative cycle makes a finite shortest path undefined for paths that can repeatedly exploit that cycle. Dijkstra’s usual correctness guarantee does not cover negative edges.
A date in an article title should not imply that the core algorithm was invented or fundamentally replaced in 2025. Research on shortest paths continues to study theoretical bounds, specialized graph structures and practical routing systems. To describe a particular 2025 breakthrough accurately, identify the paper or authors, state exactly which problem setting it addresses, and compare its assumptions and results with prior work. Do not label a result as a general replacement for Dijkstra without that evidence.
It computes distances. If the implementation stores predecessors, it can also reconstruct shortest paths.
Yes. Process only the outgoing edges of each vertex. For an undirected graph, represent each edge in both directions.
The algorithm finalises the smallest tentative distance when a vertex is selected. A later negative edge could invalidate that decision.
No, but it makes selecting the next smallest tentative distance efficient. A simple array implementation is also valid and can be suitable for small or dense graphs.
Dijkstra’s algorithm is a dependable single-source shortest-path method for graphs with non-negative weights. Understand relaxation, select the right graph representation, handle unreachable vertices correctly, and choose an alternative when negative weights or a different shortest-path problem changes the requirements.
This article was authored and reviewed by Wipidia's technical editorial desk in Jalandhar, Punjab. Every code snippet, algorithm breakdown, and strategic framework is independently tested against live production standards before publication.