Dijkstra’s Algorithm is used to find the shortest path from a starting node to all other nodes in a non-negative weighted graph, supporting both directed and undirected. BFS’s shortest path can only support unweighted graphs (reaching a node in fewer edges doesn’t mean it’s cheaper). In unweighted graphs, all the edges have the same weight 1.
Find the shortest path from A to D.
9
A → D
1 ↓ ↑ 1
B → C
1
If the weight on all edges are 1, path (A → D) is the shortest.
But with weight, path (A → B → C → D) is the shortest.
Use Cases
Purpose: Making a distance map from starting node.
map[node]distance), the distance from starting node
dist[src] = 0 to starting node itself, and math.MaxInt for all others.(distance, node)), it saves candidate nodes which are possibility can have shorter distance to neighbors than from other nodes.
Find the shortest path from A to C.
9
A → C
2 ↓ ↑ 3
B
Init:
- distanceMap {A:0, B: MAX, C: MAX}
- minHeap [(A, 0)]
Pop (A, 0) from heap,
update its neighbors' distance, because it is shorter than MAX.
- distanceMap {A:0, B: 2, C: 9}
Push the nodes we have updated into heap: (B, 2), (C, 9)
- minHeap [(B, 2), (C, 9)]
Pop (B, 2) from heap,
update its neighbors' distance, if traveling from B is shoter than from other nodes.
To C, (A → B → C) is shorter than (A → C), so update the distanceMap.
- distanceMap {A:0, B: 2, C: 5}
Push the node we have updated into heap: (C, 5)
- minHeap [(C, 5), (C, 9)]
Pop (C, 5) from heap,
- minHeap [(C, 9)]
It has no neighbor, no distanceMap update.
Pop (C, 9) from heap,
- minHeap []
This C's distance info is from (A → C), and it is not better
judging by the distanceMap (9 > 5), no need to try this path.
If we use a simple stack or queue to save, we may process farther distance node fist, which could introduce unnecessary comparing neighbors distance and distance map.
In other words, we will always want to try the shortest distance first, if we find the path distance can outweigh later, we will backtrack.
Find the shortest path from A to D.
9 9
A → B → D
2 ↓ ↑ 2
C
Use minHeap:
1. pop (A, 0), minHeap ((C, 2), (B, 9)), distanceMap {A:0, B: 9, C: 2, D: MAX}
2. pop (C, 2), minHeap ((B, 4), (B, 9)), distanceMap {A:0, B: 4, C: 2, D: MAX}
3. pop (B, 4), minHeap ((B, 9), (D, 13)), distanceMap {A:0, B: 4, C: 2, D: 13}
4. pop (B, 9), minHeap ((D, 13)), the path (A → B) is not better judging by distanceMap.
5. pop (D, 13), minHeap (), no neighbors
Use stack:
1. pop (A, 0), stack ((C, 2), (B, 9)), distanceMap {A:0, B: 9, C: 2, D: MAX}
2. pop (B, 9), stack ((C, 2), (D, 18)), distanceMap {A:0, B: 9, C: 2, D: 18}
3. pop (D, 18), stack ((C, 2)), no neighbors
4. pop (C, 2), stack ((B, 4)), distanceMap {A:0, B: 4, C: 2, D: 18}
5. pop (B, 4), stack ((D, 13)), distanceMap {A:0, B: 4, C: 2, D: 13}
6. pop (D, 13), stack (), no neighbors
It tried (A → B) first and found reaching D takes 18 distance which is not the shortest.
It introduces unnecessary step.
Another example:
Find the furthest path from A
1 1
A → B → D
9 ↓
C
Use minHeap:
1. pop (A, 0), minHeap ((B, 1), (C, 9)), distanceMap {A:0, B: 1, C: 9, D: MAX}
2. pop (B, 1), minHeap ((D, 2), (C, 9)), distanceMap {A:0, B: 1, C: 9, D: 2}
3. pop (D, 2), minHeap ((C, 9)), no neighbors
4. pop (C, 9), minHeap (), no neighbors
The **furest node will be the last one to be processed** (predictable),
so we can put a variable in the process (in 743. Network Delay Time)
to track the minimum time that a broadcaster can broadcast throughout all nodes.
Use stack:
1. pop (A, 0), stack ((B, 1), (C, 9)), distanceMap {A:0, B: 1, C: 9, D: MAX}
2. pop (C, 9), stack ((B, 1)), no neighbors
3. pop (B, 1), stack ((D, 2)), distanceMap {A:0, B: 1, C: 9, D: 2}
4. pop (D, 2), stack (), no neighbors
The last processing node **may not** the furest node.
Using a stack or a queue are about **"when" we put** the element -> unweighted graphs
Using a heap is about **"what" we put** the element into -> weighted graphs
Find the shortest path from A to D.
9 2
A → B → D
2 ↓ ↑ 9
C
(A → C) is shorter than (A → B), so we try (A → C) first,
then we found (A → C → B) outweigh, no push to heap,
then we back track to try (A → B), getting it from heap.
If we use increasing queue to save, we could remove the if cur.distance > distances[cur.node] { continue } logic in code. But managing the order of increasing queue takes more time complexity than Heap.
type Graph map[int][]Edge
type Edge struct {
node int
weight int // extra distince
}
type QueueItem struct {
node int
distance int
}
func Dijkstra(graph Graph, start int) map[int]int {
distances := make(map[int]int, len(graph))
for node := range graph {
distances[node] = math.MaxInt32
}
distances[start] = 0
h := &MinHeap{}
heap.Init(h)
heap.Push(h, QueueItem{node: start, distance: 0})
for h.Len() > 0 {
cur := heap.Pop(h).QueueItem
// this node info (other path) has been resolved
if cur.distance > distances[cur.node] {
continue
}
// once the process is at here, the shortest distance to the cur
// has been defined.
for _, neighbor := range graph[cur.node] {
// calculate the total distansce to neighbor by adding weight
neighborDist := distances[cur.node] + neighbor.weight
// if the distansce to neighbor from cur node is shorter than other node to neighbor
if neighborDist < distances[neighbor.node] {
distances[neighbor.node] = neighborDist
heap.Push(h, QueueItem{node: neighbor.node, distance: neighborDist})
}
}
}
return distances
}
type MinHeap []QueueItem
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(QueueItem)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
item := old[n-1]
*h = old[:n-1]
return item
}
https://leetcode.com/problems/network-delay-time
Last review: Sep 1, 2025 Next review: Explain it out loud before you write the code.