10.24 Testing Shortest-Path Implementations

Shortest-path implementations are prone to subtle errors.

algorithmsshortest-pathsgraphs

10.24 Testing Shortest-Path Implementations

Shortest-path implementations are prone to subtle errors. A small example may pass even when the algorithm mishandles unreachable vertices, duplicate edges, zero-weight edges, negative edges, or path reconstruction.

Testing shortest-path code requires more than checking one happy path. Good tests should exercise the assumptions of the algorithm and the invariants used in its correctness proof.

This recipe presents a practical testing strategy for BFS, Dijkstra, Bellman-Ford, Floyd-Warshall, and related shortest-path implementations.

Problem

Given a shortest-path implementation, verify that it returns correct distances, handles edge cases, and respects the algorithm's assumptions.

For example, a Dijkstra implementation should be tested against:

Zero-weight edges
Disconnected vertices
Multiple edges between the same vertices
Large weights
Graphs where a later relaxation improves a tentative distance

A Bellman-Ford implementation should also be tested against:

Negative edges
Reachable negative cycles
Unreachable negative cycles

Solution

Build a small suite of targeted graph cases.

Each test should verify one property.

Start with simple deterministic graphs whose answers can be checked by hand.

package shortestpath

import "testing"

type Edge struct {
	To     int
	Weight int
}

func TestDijkstraSimple(t *testing.T) {
	graph := [][]Edge{
		{{1, 4}, {2, 2}},
		{{3, 1}},
		{{1, 1}, {3, 5}},
		{},
	}

	got := dijkstra(graph, 0)
	want := []int{0, 3, 2, 4}

	assertEqualSlices(t, got, want)
}

A helper keeps tests readable.

func assertEqualSlices(t *testing.T, got []int, want []int) {
	t.Helper()

	if len(got) != len(want) {
		t.Fatalf("length mismatch: got %d, want %d", len(got), len(want))
	}

	for i := range got {
		if got[i] != want[i] {
			t.Fatalf("at index %d: got %d, want %d", i, got[i], want[i])
		}
	}
}

The goal is not only coverage. The goal is confidence in the algorithmic contract.

Test Unreachable Vertices

Every shortest-path implementation needs a clear convention for unreachable vertices.

BFS often uses:

-1

Weighted algorithms often use:

INF

Test both cases explicitly.

func TestDijkstraUnreachableVertex(t *testing.T) {
	graph := [][]Edge{
		{{1, 5}},
		{},
		{},
	}

	got := dijkstra(graph, 0)

	if got[2] != INF {
		t.Fatalf("vertex 2 should be unreachable: got %d", got[2])
	}
}

Unreachable vertices are common in real graphs. Do not rely on accidental behavior.

Test Zero-Weight Edges

Zero-weight edges frequently reveal incorrect visited logic.

func TestDijkstraZeroWeightEdges(t *testing.T) {
	graph := [][]Edge{
		{{1, 0}, {2, 5}},
		{{2, 0}},
		{},
	}

	got := dijkstra(graph, 0)
	want := []int{0, 0, 0}

	assertEqualSlices(t, got, want)
}

If the implementation finalizes vertices too early, this test may fail.

Zero is nonnegative, so Dijkstra must handle it correctly.

Test Multiple Edges

Graphs may contain parallel edges.

A -> B = 10
A -> B = 3

The shorter edge should win.

func TestDijkstraParallelEdges(t *testing.T) {
	graph := [][]Edge{
		{{1, 10}, {1, 3}},
		{},
	}

	got := dijkstra(graph, 0)
	want := []int{0, 3}

	assertEqualSlices(t, got, want)
}

Parallel edges occur naturally in transportation, routing, and generated graphs.

Test Late Improvements

A common Dijkstra bug is assuming the first discovered path to a vertex is final.

That is true for BFS on unweighted graphs.

It is false for Dijkstra.

func TestDijkstraLateImprovement(t *testing.T) {
	graph := [][]Edge{
		{{1, 10}, {2, 1}},
		{},
		{{1, 1}},
	}

	got := dijkstra(graph, 0)
	want := []int{0, 2, 1}

	assertEqualSlices(t, got, want)
}

The first path to vertex 1 costs 10.

The better path appears later:

0 -> 2 -> 1

with cost:

2

Test BFS Layering

For BFS, verify that distances reflect edge count, not traversal order.

func TestBFSLayers(t *testing.T) {
	graph := [][]int{
		{1, 2},
		{3},
		{3},
		{},
	}

	got := bfs(graph, 0)
	want := []int{0, 1, 1, 2}

	assertEqualSlices(t, got, want)
}

Also test a case where DFS would produce the wrong shortest distance. This guards against accidentally using stack-like behavior.

Test Bellman-Ford Negative Edges

Bellman-Ford should handle negative edges without negative cycles.

func TestBellmanFordNegativeEdges(t *testing.T) {
	edges := []WeightedEdge{
		{0, 1, 4},
		{0, 2, 2},
		{2, 1, -3},
	}

	dist, hasCycle := bellmanFord(3, edges, 0)

	if hasCycle {
		t.Fatalf("unexpected negative cycle")
	}

	want := []int{0, -1, 2}
	assertEqualSlices(t, dist, want)
}

This test would be invalid for Dijkstra but required for Bellman-Ford.

Test Reachable Negative Cycles

Bellman-Ford must detect a negative cycle reachable from the source.

func TestBellmanFordReachableNegativeCycle(t *testing.T) {
	edges := []WeightedEdge{
		{0, 1, 1},
		{1, 2, -3},
		{2, 0, 1},
	}

	_, hasCycle := bellmanFord(3, edges, 0)

	if !hasCycle {
		t.Fatalf("expected reachable negative cycle")
	}
}

The cycle cost is:

1 + (-3) + 1 = -1

No finite shortest path exists.

Test Unreachable Negative Cycles

A source-based Bellman-Ford implementation should not report negative cycles that cannot be reached from the source.

func TestBellmanFordUnreachableNegativeCycle(t *testing.T) {
	edges := []WeightedEdge{
		{0, 1, 5},
		{2, 3, -10},
		{3, 2, 1},
	}

	_, hasCycle := bellmanFord(4, edges, 0)

	if hasCycle {
		t.Fatalf("unreachable negative cycle should not affect source-based shortest paths")
	}
}

This test verifies the reachability guard:

if dist[edge.From] == INF {
	continue
}

Test Path Reconstruction

Distances can be correct while paths are wrong.

Test reconstruction separately.

func TestBuildPath(t *testing.T) {
	parent := []int{
		-1,
		0,
		0,
		1,
	}

	got := buildPath(parent, 0, 3)
	want := []int{0, 1, 3}

	assertEqualSlices(t, got, want)
}

Also test unreachable targets.

func TestBuildPathUnreachable(t *testing.T) {
	parent := []int{
		-1,
		0,
		-1,
	}

	got := buildPath(parent, 0, 2)

	if got != nil {
		t.Fatalf("expected nil path for unreachable target")
	}
}

Do not assume distance tests automatically validate predecessor logic.

Cross-Check Algorithms

A strong testing strategy is to compare algorithms on overlapping domains.

For a graph with nonnegative weights:

Dijkstra and Bellman-Ford should agree.

For a small graph with all-pairs distances:

Repeated Dijkstra and Floyd-Warshall should agree.

Example:

func TestDijkstraMatchesBellmanFord(t *testing.T) {
	graph := [][]Edge{
		{{1, 4}, {2, 1}},
		{{3, 2}},
		{{1, 1}, {3, 7}},
		{},
	}

	edges := edgeListFromGraph(graph)

	got := dijkstra(graph, 0)
	want, hasCycle := bellmanFord(len(graph), edges, 0)

	if hasCycle {
		t.Fatalf("unexpected negative cycle")
	}

	assertEqualSlices(t, got, want)
}

This technique is especially useful when one implementation is simple but slow and another is optimized.

Use Brute Force on Small Graphs

For very small graphs, brute force can serve as an oracle.

Generate all simple paths from source to target and compute the minimum cost.

This is exponential, but for:

V <= 8

it is often fine in tests.

The brute-force version should not be used in production. Its job is to validate optimized implementations.

Property-Based Testing

Property-based tests generate many random graphs and check invariants.

Useful properties include:

dist[source] = 0
dist[v] <= dist[u] + w for every edge u -> v
unreachable vertices remain INF or -1
reconstructed path cost equals dist[target]
Dijkstra equals Bellman-Ford on nonnegative graphs

These tests catch cases that hand-written tests miss.

Even a small randomized suite can expose subtle bugs.

Boundary Tests

Include boundary cases.

Empty graph
Single vertex
Source equals target
Disconnected graph
Graph with self-loop
Graph with parallel edges
Very large edge weights
Zero-weight edges

These cases often reveal incorrect initialization or overflow.

Overflow Tests

If weights can be large, test values near the integer limit.

Bad code may do:

candidate := dist[u] + weight

without checking:

if dist[u] == INF {
	continue
}

This can overflow.

Use a safe infinity value and guard arithmetic involving infinity.

Test Algorithm Assumptions

Each algorithm has assumptions.

Algorithm Assumption to Test
BFS All edges have equal cost
Dijkstra All weights are nonnegative
Bellman-Ford Negative cycles are detected
Floyd-Warshall Matrix initialization is correct
DAG shortest paths Graph is acyclic
0-1 BFS Weights are only 0 or 1

Tests should make these assumptions visible.

When invalid input is possible, decide whether the implementation should reject it or document that behavior is undefined.

Discussion

Good shortest-path tests are not large. They are precise.

A graph with four vertices can test late relaxation.

A graph with three vertices can test a negative cycle.

A graph with two parallel edges can test duplicate-edge handling.

Small tests are easier to inspect, easier to debug, and more likely to reveal the exact invariant that failed.

Large random tests are useful later, but they should supplement hand-crafted cases rather than replace them.

Takeaway

Testing shortest-path algorithms requires targeting the invariants behind the algorithms. Verify unreachable vertices, zero-weight edges, parallel edges, late improvements, negative edges, negative cycles, path reconstruction, and boundary cases. Cross-check algorithms where their domains overlap, and use brute force or property-based testing on small graphs when possible. A reliable test suite should make the algorithm's assumptions explicit and catch the subtle failures that simple examples miss.