The challenge
Compute shortest distances from one source in a weighted graph whose edge weights are all nonnegative.
Negative weights invalidate the settling argument. Use Bellman–Ford when negative edges may occur.
Example
From A: A:0, B:3, C:4, D:7, E:8, F:1. A → F → B beats the direct A → B edge.
Use the walkthrough below to inspect the input and each state change.
See Dijkstra, step by step
Follow the edges. Watch the state change.
Directed · 6 vertices · 7 edgesA = 0, B = 1, …
CurrentVisited / acceptedUnvisited
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
Step 01 / 17
Set distance[A] = 0.
All edge weights must be nonnegative. Unreached vertices begin at infinity.
push(0, A)Min-priority queue · smallest first
A:0
View input edges
A → B (4) · A → F (1) · F → B (2) · B → C (1) · F → E (8) · C → D (3) · D → E (1)
Source: A. Adjacency entries follow this edge order.
Put it into code
Always process the smallest tentative distance; ignore old queue entries.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
from heapq import heappop, heappush
from math import inf
def dijkstra(adj, source):
# adj[u] contains (v, weight); ALL weights >= 0.
distance = [inf] * len(adj)
distance[source] = 0
heap = [(0, source)]
while heap:
d, u = heappop(heap)
if d != distance[u]:
continue # Discard an outdated queue entry.
for v, weight in adj[u]:
candidate = d + weight
if candidate < distance[v]:
distance[v] = candidate
heappush(heap, (candidate, v))
return distance#include <functional>
#include <queue>
#include <utility>
#include <vector>
using ll = long long;
constexpr ll INF = (1LL << 60);
std::vector<ll> dijkstra(
const std::vector<std::vector<std::pair<int, ll>>>& adj,
int source) { // All weights >= 0; path sums < INF.
std::vector<ll> distance(adj.size(), INF);
using State = std::pair<ll, int>;
std::priority_queue<State, std::vector<State>,
std::greater<State>> heap;
distance[source] = 0;
heap.push({0, source});
while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
if (d != distance[u]) continue;
for (auto [v, weight] : adj[u]) {
if (d + weight < distance[v]) {
distance[v] = d + weight;
heap.push({distance[v], v});
}
}
}
return distance;
}