10.4 Implementing Dijkstra with Priority Queue Variants

The previous recipe used Dijkstra’s algorithm with a binary heap and lazy deletion. That version is the usual choice in production code because it is simple, fast enough for most sparse graphs, and available in standard libraries.

This recipe compares three implementation variants:

1. Linear scan
2. Binary heap with lazy deletion
3. Indexed priority queue with decrease-key

The algorithmic idea remains the same. The difference is how we choose the next vertex with the smallest tentative distance.

Problem

Given a graph with nonnegative edge weights, choose a Dijkstra implementation that fits the graph size, graph density, and available data structures.

The shortest path logic is unchanged:

Initialize distance[source] = 0
Repeatedly choose the unsettled vertex with minimum distance
Relax its outgoing edges

The implementation question is:

How do we find the minimum-distance vertex efficiently?

Solution 1: Linear Scan

For dense graphs or small inputs, the simplest implementation scans all vertices to find the unsettled vertex with the smallest distance.

package main

import "fmt"

type Edge struct {
	To     int
	Weight int
}

func dijkstraLinear(graph [][]Edge, source int) []int {
	const INF = int(1e18)

	n := len(graph)
	dist := make([]int, n)
	used := make([]bool, n)

	for i := range dist {
		dist[i] = INF
	}

	dist[source] = 0

	for step := 0; step < n; step++ {
		v := -1

		for i := 0; i < n; i++ {
			if used[i] {
				continue
			}

			if v == -1 || dist[i] < dist[v] {
				v = i
			}
		}

		if v == -1 || dist[v] == INF {
			break
		}

		used[v] = true

		for _, edge := range graph[v] {
			newDistance := dist[v] + edge.Weight
			if newDistance < dist[edge.To] {
				dist[edge.To] = 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(dijkstraLinear(graph, 0))
}

Output:

[0 4 2 5]

This version avoids heap code entirely. It is often easier to debug and can perform well when the graph is dense enough that the edge count is close to V².

Solution 2: Binary Heap with Lazy Deletion

For sparse graphs, a binary heap usually performs better. Since Go’s standard heap package does not provide a direct decrease-key operation, we push a new entry whenever a distance improves. Old entries are ignored when popped.

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 dijkstraHeap(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 := current.Distance + 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(dijkstraHeap(graph, 0))
}

Output:

[0 4 2 5]

This is the most common general-purpose version.

Solution 3: Indexed Priority Queue

An indexed priority queue stores the current heap position for each vertex. When a distance improves, the existing heap item is updated and moved upward instead of inserting a duplicate.

This gives a cleaner theoretical implementation but requires more code.

type IndexedItem struct {
	Vertex   int
	Distance int
	Index    int
}

type IndexedPriorityQueue struct {
	items []*IndexedItem
	pos   []int
}

func NewIndexedPriorityQueue(n int) *IndexedPriorityQueue {
	pos := make([]int, n)
	for i := range pos {
		pos[i] = -1
	}

	return &IndexedPriorityQueue{
		items: []*IndexedItem{},
		pos:   pos,
	}
}

func (pq *IndexedPriorityQueue) Len() int {
	return len(pq.items)
}

func (pq *IndexedPriorityQueue) less(i, j int) bool {
	return pq.items[i].Distance < pq.items[j].Distance
}

func (pq *IndexedPriorityQueue) swap(i, j int) {
	pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
	pq.items[i].Index = i
	pq.items[j].Index = j
	pq.pos[pq.items[i].Vertex] = i
	pq.pos[pq.items[j].Vertex] = j
}

func (pq *IndexedPriorityQueue) push(vertex int, distance int) {
	item := &IndexedItem{
		Vertex:   vertex,
		Distance: distance,
		Index:    len(pq.items),
	}

	pq.items = append(pq.items, item)
	pq.pos[vertex] = item.Index
	pq.up(item.Index)
}

func (pq *IndexedPriorityQueue) pop() IndexedItem {
	top := pq.items[0]
	last := pq.items[len(pq.items)-1]

	pq.items[0] = last
	pq.items[0].Index = 0
	pq.pos[pq.items[0].Vertex] = 0

	pq.items = pq.items[:len(pq.items)-1]
	pq.pos[top.Vertex] = -1

	if len(pq.items) > 0 {
		pq.down(0)
	}

	return *top
}

func (pq *IndexedPriorityQueue) decrease(vertex int, distance int) {
	i := pq.pos[vertex]

	if i == -1 {
		pq.push(vertex, distance)
		return
	}

	if distance >= pq.items[i].Distance {
		return
	}

	pq.items[i].Distance = distance
	pq.up(i)
}

func (pq *IndexedPriorityQueue) up(i int) {
	for i > 0 {
		parent := (i - 1) / 2

		if !pq.less(i, parent) {
			break
		}

		pq.swap(i, parent)
		i = parent
	}
}

func (pq *IndexedPriorityQueue) down(i int) {
	for {
		left := 2*i + 1
		right := 2*i + 2
		best := i

		if left < len(pq.items) && pq.less(left, best) {
			best = left
		}

		if right < len(pq.items) && pq.less(right, best) {
			best = right
		}

		if best == i {
			break
		}

		pq.swap(i, best)
		i = best
	}
}

Dijkstra then becomes:

func dijkstraIndexedHeap(graph [][]Edge, source int) []int {
	const INF = int(1e18)

	n := len(graph)
	dist := make([]int, n)
	settled := make([]bool, n)

	for i := range dist {
		dist[i] = INF
	}

	dist[source] = 0

	pq := NewIndexedPriorityQueue(n)
	pq.decrease(source, 0)

	for pq.Len() > 0 {
		current := pq.pop()
		v := current.Vertex

		if settled[v] {
			continue
		}

		settled[v] = true

		for _, edge := range graph[v] {
			if settled[edge.To] {
				continue
			}

			newDistance := dist[v] + edge.Weight

			if newDistance >= dist[edge.To] {
				continue
			}

			dist[edge.To] = newDistance
			pq.decrease(edge.To, newDistance)
		}
	}

	return dist
}

The indexed heap uses less heap memory than lazy deletion when many distance improvements occur, but the implementation is more error-prone.

Choosing a Variant

Use the simplest variant that satisfies the constraints.

Variant	Best For	Time Complexity	Notes
Linear scan	Small or dense graphs	O(V² + E)	Simple and predictable
Binary heap, lazy deletion	Sparse graphs	O((V + E) log E)	Practical default
Indexed heap	Large graphs with many updates	O((V + E) log V)	More code, less duplication

For most application code, binary heap with lazy deletion is the right default. For programming contests, it is also the safest implementation under time pressure. For dense graphs, the linear version may be competitive or faster because it avoids heap overhead.

Discussion

Dijkstra has two separate concerns:

1. The correctness rule
2. The data structure used to select the next vertex

The correctness rule says that the unsettled vertex with the smallest tentative distance can be finalized because all edge weights are nonnegative.

The data structure only changes how efficiently we find that vertex.

This separation is useful. When debugging, first verify the algorithmic invariant. Then inspect the priority queue behavior.

The usual invariant is:

All settled vertices have final shortest-path distances.

The heap may contain stale data. That is acceptable in the lazy-deletion version because stale entries are discarded before relaxation.

if current.Distance != dist[current.Vertex] {
	continue
}

That one condition is the difference between a correct lazy heap and a subtle bug.

Common Mistakes

Do not compare heap entries by vertex number. The priority must be distance.

Do not mark a vertex settled when it is pushed. A better path may still be discovered before it is popped.

Do not use an indexed heap unless you have tests for heap position updates. One wrong pos assignment can corrupt the queue.

Do not assume O((V + E) log V) and O((V + E) log E) matter much in ordinary sparse graphs. Constants, memory access, and code complexity usually dominate.

Do not forget overflow. If INF is close to the maximum integer value, dist[v] + weight can wrap.

Testing

Good Dijkstra tests should include:

func testGraph() [][]Edge {
	return [][]Edge{
		{{1, 4}, {2, 2}},
		{{0, 4}, {3, 1}},
		{{0, 2}, {3, 3}},
		{{1, 1}, {2, 3}},
	}
}

Expected distances from 0:

[0 4 2 5]

Also include:

Disconnected vertices
Multiple edges between the same vertices
A zero-weight edge
A graph with one vertex
A graph where a later relaxation improves a distance

These cases exercise the queue logic, not just the shortest-path formula.

Takeaway

Dijkstra’s algorithm is defined by its greedy settling rule, not by a specific heap implementation. A linear scan is often enough for small or dense graphs. A binary heap with lazy deletion is the standard practical choice for sparse graphs. An indexed heap gives cleaner asymptotic behavior but requires more code and stronger tests.