10.25 Debugging and Optimizing Shortest-Path Code

Shortest-path code usually fails in predictable ways.

The algorithm may be conceptually correct, but the implementation mishandles the queue, marks vertices at the wrong time, overflows an integer, reconstructs paths incorrectly, or applies the algorithm outside its assumptions.

This final recipe provides a practical checklist for debugging and optimizing shortest-path implementations.

Problem

Given a shortest-path implementation that is wrong, slow, or memory-heavy, identify the source of the problem and apply the right fix.

Typical symptoms include:

Distances are too large
Distances are too small
Unreachable vertices look reachable
The algorithm never terminates
The path is correct but the cost is wrong
The cost is correct but the path is wrong
Runtime is much slower than expected
Memory usage grows unexpectedly

Each symptom points to a small set of likely causes.

Solution

Debug shortest-path code by checking the algorithm's invariants in order:

1. Graph representation
2. Initialization
3. Relaxation logic
4. Queue or priority queue behavior
5. Visited or settled rules
6. Overflow handling
7. Path reconstruction
8. Algorithm assumptions

Do not start by rewriting the whole algorithm. Shortest-path bugs are often one-line errors.

Check the Graph Representation

Many bugs come from encoding the graph incorrectly.

For an undirected graph, every edge must usually be inserted twice:

graph[u] = append(graph[u], Edge{To: v, Weight: w})
graph[v] = append(graph[v], Edge{To: u, Weight: w})

For a directed graph, insert only one edge:

graph[u] = append(graph[u], Edge{To: v, Weight: w})

Mixing these cases changes the problem.

Also verify vertex numbering.

If input vertices are 1-based:

1 2 3 4

but slices are 0-based:

0 1 2 3

convert at the boundary:

u--
v--

Do not scatter this conversion throughout the algorithm.

Verify Initialization

Initialization should be boring and explicit.

For BFS:

for i := range dist {
	dist[i] = -1
}

dist[source] = 0
queue := []int{source}

For weighted shortest paths:

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

dist[source] = 0

For parent arrays:

for i := range parent {
	parent[i] = -1
}

Common initialization errors include:

• Forgetting to set dist[source] = 0
• Leaving distances at Go's default zero value
• Forgetting to initialize parents
• Using 0 to mean both reachable distance and unreachable distance
• Allocating arrays with the wrong size

If all distances appear too small, initialization is the first suspect.

Inspect Relaxation

Relaxation is the core operation.

For an edge:

u -> v with weight w

the update should be:

candidate := dist[u] + w

if candidate < dist[v] {
	dist[v] = candidate
	parent[v] = u
}

A wrong comparison direction silently breaks the algorithm.

Incorrect:

if candidate > dist[v] {
	dist[v] = candidate
}

That computes something closer to a longest path, and usually not even correctly.

Also check that the target vertex is updated:

dist[edge.To] = candidate

not the current vertex.

Relaxation bugs are usually small but severe.

Guard Infinity Arithmetic

Never add a weight to infinity.

Incorrect:

candidate := dist[u] + w

when:

dist[u] = INF

If INF is close to the maximum integer, this can overflow.

Correct:

if dist[u] == INF {
	continue
}

candidate := dist[u] + w

Use an infinity value that leaves room for addition.

const INF = int(1 << 60)

instead of:

const INF = math.MaxInt

when edge weights will be added.

Debug BFS Queue Behavior

BFS requires a FIFO queue.

Correct:

head := 0

for head < len(queue) {
	v := queue[head]
	head++

	for _, next := range graph[v] {
		...
	}
}

Incorrect queue behavior can turn BFS into DFS or cause repeated processing.

Mark vertices when they are enqueued:

if dist[next] == -1 {
	dist[next] = dist[v] + 1
	queue = append(queue, next)
}

Do not wait until dequeue time to mark them. That allows the same vertex to enter the queue multiple times.

Debug Dijkstra Priority Queues

The priority queue must order by distance.

Correct:

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].Distance < pq[j].Distance
}

Incorrect:

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].Vertex < pq[j].Vertex
}

This compiles and runs but destroys correctness.

With lazy deletion, stale heap entries must be ignored:

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

or:

if current.Distance > dist[current.Vertex] {
	continue
}

Without this check, outdated paths may relax edges incorrectly or waste large amounts of time.

Do not mark a vertex visited when it is pushed into the heap. Mark it only when popped with its best distance, or use the lazy-deletion check and avoid a separate visited array.

Debug Bellman-Ford

Bellman-Ford should perform:

V - 1

full passes over all edges.

A common off-by-one error uses too few passes.

Correct:

for i := 0; i < vertices-1; i++ {
	for _, edge := range edges {
		...
	}
}

For negative-cycle detection, run one additional pass.

for _, edge := range edges {
	if dist[edge.From] == INF {
		continue
	}

	if dist[edge.From]+edge.Weight < dist[edge.To] {
		return true
	}
}

If unreachable negative cycles are being reported, the reachability guard is probably missing.

Debug Floyd-Warshall

The loop order matters.

Correct:

for k := 0; k < n; k++ {
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			...
		}
	}
}

The outer loop must be the intermediate vertex.

Also verify matrix initialization:

dist[i][i] = 0

and:

dist[u][v] = min(dist[u][v], w)

when parallel edges exist.

Do not overwrite a shorter parallel edge with a longer one.

Debug Path Reconstruction

If distances are correct but paths are wrong, inspect parent updates.

The parent must be updated only when the distance improves:

if candidate < dist[v] {
	dist[v] = candidate
	parent[v] = u
}

When reconstructing, walk backward:

for v := target; v != -1; v = parent[v] {
	path = append(path, v)
}

then reverse.

Check unreachable targets before reconstruction:

if dist[target] == INF {
	return nil
}

or:

if parent[target] == -1 && source != target {
	return nil
}

Otherwise, you may return a meaningless path containing only the target.

Detect Algorithm Mismatch

Many failures are not implementation bugs. The wrong algorithm was selected.

Symptom	Likely Cause
BFS gives wrong answer	Graph has weighted edges
Dijkstra gives wrong answer	Negative edge exists
Bellman-Ford reports no finite answer	Reachable negative cycle
Floyd-Warshall too slow	Graph too large
A* returns nonoptimal path	Heuristic overestimates
0-1 BFS wrong	Edge weight larger than 1

Always verify assumptions before debugging code.

Add Trace Output

Small trace logs make shortest-path bugs visible.

For relaxation:

fmt.Printf(
	"relax %d -> %d: old=%d candidate=%d\n",
	u,
	v,
	dist[v],
	candidate,
)

For priority queue pops:

fmt.Printf(
	"pop vertex=%d distance=%d current=%d\n",
	item.Vertex,
	item.Distance,
	dist[item.Vertex],
)

For BFS:

fmt.Printf(
	"visit %d distance=%d\n",
	next,
	dist[next],
)

Keep trace output temporary and run it only on tiny graphs.

Optimize Graph Storage

For large graphs, representation matters.

Adjacency lists are usually best for sparse graphs:

[][]Edge

They use:

O(V + E)

memory.

Adjacency matrices use:

O(V²)

memory.

They are appropriate for dense graphs or Floyd-Warshall, but wasteful for sparse graphs.

For very large inputs, preallocate adjacency lists when degrees are known.

graph[u] = make([]Edge, 0, degree[u])

This reduces allocations.

Optimize Priority Queue Usage

Lazy deletion may push many heap entries.

This is usually acceptable, but it can increase memory.

If memory becomes a bottleneck, consider:

• Indexed priority queue
• Pairing heap
• Custom binary heap
• Reducing duplicate relaxations
• Switching to linear-scan Dijkstra for dense graphs

Do not optimize the heap before profiling. Many shortest-path programs spend more time parsing input than maintaining the heap.

Optimize for Early Exit

When only one target matters, stop early.

In BFS:

if v == target {
	return dist[v]
}

In Dijkstra:

if current.Vertex == target {
	return current.Distance
}

This is correct when the vertex is popped or dequeued under the algorithm's normal finalization rule.

Do not stop when the target is merely discovered in Dijkstra. A shorter path may still appear.

Optimize State-Space Search

For state-space problems, the number of states dominates performance.

Optimization usually means reducing state count.

Useful techniques include:

• Compact state encoding
• Bitmasks for sets of keys
• Integer IDs instead of structs in maps
• Pruning impossible states
• Avoiding unnecessary state fields
• Using A* with an admissible heuristic
• Bidirectional search when source and target are known

A faster queue rarely compensates for a poorly designed state representation.

Handle Large Inputs

For competitive programming and data-heavy systems, input processing matters.

Use buffered input.

Avoid excessive string parsing.

Prefer integer vertex IDs.

Avoid storing full paths inside queue entries unless necessary.

Store parents separately when possible.

For K-shortest paths or path enumeration, full path storage may be unavoidable, but it should be deliberate.

Common Performance Traps

Do not remove from the front of a Go slice repeatedly:

queue = queue[1:]

Use a head index instead.

Do not copy large path slices in every search state unless the problem requires it.

Do not store graph nodes as strings in inner loops when integers are available.

Do not use recursion for very deep graph traversal if stack depth may be large.

Do not use Floyd-Warshall when V is too large for a V × V matrix.

A Debugging Checklist

Before trusting shortest-path code, verify:

Graph direction is correct
Vertex indexing is correct
Distances are initialized correctly
Source distance is zero
Unreachable convention is consistent
Relaxation comparison uses <
Infinity arithmetic is guarded
Queue or heap ordering is correct
Visited or settled timing is correct
Parents update with distance improvements
Algorithm assumptions match edge weights
Path reconstruction handles unreachable targets
Overflow is impossible or guarded

This checklist catches most defects.

Takeaway

Shortest-path bugs usually come from broken invariants rather than from the high-level algorithm. Debug the representation, initialization, relaxation, frontier ordering, visited rules, overflow checks, and path reconstruction before rewriting the algorithm. Optimize only after confirming correctness, and prefer structural optimizations such as better state modeling, early exit, appropriate graph storage, and the right algorithm for the graph's assumptions.