10.3 Solving Nonnegative Weighted Shortest Paths with Dijkstra's Algorithm
Breadth-first search works because every edge contributes the same cost.
10.3 Solving Nonnegative Weighted Shortest Paths with Dijkstra's Algorithm
Breadth-first search works because every edge contributes the same cost. Once edge weights become arbitrary positive values, distance layers disappear. A path containing fewer edges may be more expensive than a path containing many edges.
Consider the following graph:
A --1-- B --1-- D
\ ^
\ /
5 1
\ /
C -----
The path:
A -> C -> D
contains two edges and costs:
5 + 1 = 6
The path:
A -> B -> D
also contains two edges but costs:
1 + 1 = 2
The number of edges is no longer sufficient. We must optimize total path cost.
Dijkstra's algorithm solves this problem for graphs whose edge weights are nonnegative.
Problem
Given a weighted graph with nonnegative edge weights and a source vertex, compute the minimum path cost from the source to every reachable vertex.
For example:
4
A ------ B
| |
2 | | 1
| |
C ------ D
3
Starting from A, determine the shortest distance to every vertex.
Solution
Dijkstra repeatedly selects the undiscovered vertex with the smallest known distance.
A priority queue maintains candidate vertices ordered by distance.
package main
import (
"container/heap"
"fmt"
)
type Edge struct {
To int
Weight int
}
type Item struct {
Vertex int
Distance int
}
type PriorityQueue []Item
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].Distance < pq[j].Distance
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x any) {
*pq = append(*pq, x.(Item))
}
func (pq *PriorityQueue) Pop() any {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[:n-1]
return item
}
func dijkstra(graph [][]Edge, source int) []int {
const INF = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = INF
}
dist[source] = 0
pq := &PriorityQueue{}
heap.Init(pq)
heap.Push(pq, Item{
Vertex: source,
Distance: 0,
})
for pq.Len() > 0 {
current := heap.Pop(pq).(Item)
if current.Distance > dist[current.Vertex] {
continue
}
for _, edge := range graph[current.Vertex] {
newDistance := dist[current.Vertex] + edge.Weight
if newDistance >= dist[edge.To] {
continue
}
dist[edge.To] = newDistance
heap.Push(pq, Item{
Vertex: edge.To,
Distance: newDistance,
})
}
}
return dist
}
func main() {
graph := [][]Edge{
{{1, 4}, {2, 2}},
{{0, 4}, {3, 1}},
{{0, 2}, {3, 3}},
{{1, 1}, {2, 3}},
}
fmt.Println(dijkstra(graph, 0))
}
Output:
[0 4 2 5]
How It Works
The key observation behind Dijkstra is remarkably simple.
Suppose we know the following tentative distances:
A = 0
B = 4
C = 2
D = ∞
The smallest undiscovered distance belongs to C.
A = 0
C = 2
Since every edge weight is nonnegative, no future path can reduce the distance to C.
Any alternative route must first pass through a vertex whose distance is at least 2, then add one or more nonnegative edges.
Consequently, the current distance to C is already optimal.
Dijkstra repeatedly applies this reasoning:
- Extract the closest undiscovered vertex.
- Declare its distance final.
- Relax all outgoing edges.
- Repeat.
The algorithm gradually expands a region of vertices whose shortest paths are known with certainty.
Understanding Relaxation
The central operation in Dijkstra is edge relaxation.
Suppose we know:
distance[A] = 5
and there is an edge:
A --3--> B
The route through A implies a possible distance:
5 + 3 = 8
If the current distance to B is larger than 8, we improve it.
newDistance := dist[A] + weight
if newDistance < dist[B] {
dist[B] = newDistance
}
This update is called relaxation.
Every shortest path algorithm in this chapter relies on repeated relaxation.
Why the Priority Queue Matters
A naive implementation scans every vertex to find the smallest tentative distance.
Find minimum vertex
Relax edges
Repeat
This produces:
O(V²)
time complexity.
A binary heap allows extraction of the minimum-distance vertex in:
O(log V)
time.
For sparse graphs, this dramatically improves performance.
The resulting complexity becomes:
O((V + E) log V)
which is the standard form used in practice.
Lazy Deletion
Many implementations push multiple copies of the same vertex into the heap.
For example:
D = 15
Later:
D = 9
Both entries remain in the heap.
When the older value appears, the algorithm ignores it:
if current.Distance > dist[current.Vertex] {
continue
}
This technique is called lazy deletion.
It avoids implementing a decrease-key operation while preserving correctness.
Modern production code frequently uses this approach because it is simple and efficient.
Discussion
Dijkstra's correctness depends entirely on one assumption:
All edge weights must be nonnegative.
Suppose a negative edge exists.
A -> B = 5
A -> C = 10
C -> B = -20
Dijkstra may finalize:
B = 5
before discovering:
A -> C -> B = -10
The algorithm's core invariant collapses.
Whenever negative weights are possible, Bellman-Ford or another algorithm must be used instead.
Complexity
Using an adjacency list and binary heap:
| Operation | Complexity |
|---|---|
| Heap insertion | O(log V) |
| Heap extraction | O(log V) |
| Edge relaxation | O(1) |
| Total running time | O((V + E) log V) |
| Memory usage | O(V + E) |
For sparse graphs, this is one of the most efficient exact shortest-path algorithms available.
Common Mistakes
Using Dijkstra on graphs with negative edges is the most common error.
Marking vertices as permanently visited too early often produces incorrect results when lazy deletion is used.
Using an adjacency matrix instead of an adjacency list can significantly increase running time for sparse graphs.
Choosing a value for infinity that is too small can cause integer overflow or incorrect comparisons.
Forgetting that shortest paths may contain many edges often leads developers to optimize edge count instead of path cost.
Takeaway
Dijkstra's algorithm generalizes the shortest-path ideas introduced by BFS to weighted graphs with nonnegative edge costs. Its central insight is that the smallest tentative distance can be finalized immediately because nonnegative weights prevent future improvements. Combined with a priority queue and edge relaxation, this produces an efficient algorithm that forms the foundation of routing systems, navigation engines, network optimization tools, and many other real-world graph applications.