10.17 Finding K Shortest Paths

Most shortest-path algorithms answer a single question:

What is the shortest path from the source to the destination?

In many practical systems, one path is not enough.

A navigation application may want alternative routes. A logistics system may need backup delivery plans. A network router may require secondary paths in case of failures. A recommendation engine may want multiple high-quality options rather than a single optimal answer.

These problems lead to the K shortest paths problem.

Instead of finding only the best path, we want:

1st shortest path
2nd shortest path
3rd shortest path
...
Kth shortest path

ordered by total cost.

This recipe introduces the fundamental techniques used to compute multiple shortest paths.

Problem

Given a weighted graph, a source vertex, a destination vertex, and an integer:

find the first:

shortest paths between the source and destination.

Consider:

A -> B -> D
A -> C -> D
A -> E -> D

with costs:

A -> B -> D = 3
A -> C -> D = 4
A -> E -> D = 5

The desired output is:

1st: A -> B -> D
2nd: A -> C -> D
3rd: A -> E -> D

ordered by path cost.

Solution

A useful starting point is a modified version of Dijkstra's algorithm.

Instead of recording only the best distance to each vertex, record multiple distances.

A vertex may be processed several times as long as fewer than:

shortest paths to that vertex have been discovered.

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct {
	To     int
	Weight int
}

type State struct {
	Vertex   int
	Distance int
}

type PriorityQueue []State

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.(State))
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)

	item := old[n-1]
	*pq = old[:n-1]

	return item
}

func kShortestDistances(
	graph [][]Edge,
	source int,
	target int,
	k int,
) []int {

	pq := &PriorityQueue{}
	heap.Init(pq)

	heap.Push(pq, State{
		Vertex:   source,
		Distance: 0,
	})

	visits := make([]int, len(graph))
	var result []int

	for pq.Len() > 0 {
		current := heap.Pop(pq).(State)

		visits[current.Vertex]++

		if current.Vertex == target {
			result = append(
				result,
				current.Distance,
			)

			if len(result) == k {
				return result
			}
		}

		if visits[current.Vertex] > k {
			continue
		}

		for _, edge := range graph[current.Vertex] {
			heap.Push(pq, State{
				Vertex: edge.To,
				Distance: current.Distance +
					edge.Weight,
			})
		}
	}

	return result
}

func main() {
	graph := [][]Edge{
		{{1, 1}, {2, 2}},
		{{3, 2}},
		{{3, 2}},
		{},
	}

	fmt.Println(
		kShortestDistances(
			graph,
			0,
			3,
			3,
		),
	)
}

This approach works well for many competitive-programming problems and introduces the central idea behind K-shortest-path algorithms.

Understanding the Difference from Dijkstra

Ordinary Dijkstra maintains:

Best distance to each vertex

Once a vertex is finalized:

No better path exists.

The vertex never needs to be revisited.

K-shortest-path algorithms relax this rule.

Suppose:

Shortest path = 10

The second shortest path might be:

The third shortest path might be:

All of them remain useful.

Consequently, vertices may appear multiple times in the priority queue.

The algorithm intentionally preserves alternatives.

Visualizing the Search

Consider:

A -> B -> D
A -> C -> D

with costs:

A -> B -> D = 3
A -> C -> D = 4

Ordinary Dijkstra discovers:

and stops.

K-shortest-path search continues.

The priority queue evolves:

3
4
...

Each valid route emerges in increasing order of cost.

The process resembles repeatedly peeling layers from the shortest-path landscape.

Why Multiple Visits Are Necessary

Suppose:

A -> B = 1
A -> C = 2
B -> D = 2
C -> D = 2

The destination receives:

3
4

through different routes.

If vertices were finalized after the first visit:

D = 3

the alternative path would never be discovered.

Allowing multiple visits preserves additional solutions.

This is the essential difference between shortest-path and K-shortest-path algorithms.

Distinct Paths Versus Distinct Distances

An important distinction exists.

Consider:

A -> B -> D
A -> C -> D

Both routes may have cost:

Should these count as:

One solution

or:

Two solutions

Different applications answer differently.

Interpretation	Result
Distinct costs	One answer
Distinct paths	Two answers

Most K-shortest-path algorithms count paths rather than distances.

The exact definition should always be specified.

Path Reconstruction

Distances alone are rarely sufficient.

Store predecessor information inside the queue state.

type State struct {
	Vertex   int
	Distance int
	Path     []int
}

Whenever an edge is expanded:

newPath := append(
	append([]int{}, current.Path...),
	edge.To,
)

The resulting state carries its entire route.

When the destination is reached:

Distance
+
Actual path

become available immediately.

For small values of:

this approach is often adequate.

Yen's Algorithm

The previous approach is useful but not always optimal.

A classic algorithm for K shortest simple paths is Yen's algorithm.

The idea is:

Compute the shortest path.
Generate candidate deviations.
Select the next shortest candidate.
Repeat until K paths are found.

Suppose:

A -> B -> C -> D

is the shortest path.

Yen systematically explores deviations:

A -> X -> ...
A -> B -> Y -> ...
A -> B -> C -> Z -> ...

while avoiding duplicate paths.

This approach guarantees ordered simple paths.

Eppstein's Algorithm

For large values of:

even Yen's algorithm can become expensive.

Eppstein's algorithm builds an auxiliary structure around a shortest-path tree and generates paths efficiently.

The algorithm is considerably more sophisticated but achieves:

O(E + V log V + K log K)

time complexity.

Many research systems use Eppstein-style techniques when large numbers of alternative paths are required.

Relationship to Shortest-Path Trees

Ordinary shortest-path algorithms construct a tree.

Source
├─ Path A
├─ Path B
└─ Path C

The shortest route to every vertex lies inside this tree.

K-shortest-path algorithms explore paths that leave the tree temporarily and rejoin later.

Alternative routes often differ only slightly from the optimal path.

This observation motivates many advanced algorithms.

Rather than rebuilding paths from scratch, they generate controlled deviations.

Applications in Routing

Consider a road network.

The shortest route might encounter:

Traffic
Construction
Accident

A navigation system often prefers:

Best route
Second-best route
Third-best route

presented simultaneously.

The user can then choose.

This requirement naturally leads to K-shortest-path algorithms.

The same pattern appears in communication networks and logistics systems.

Discussion

K-shortest-path problems illustrate an important shift in optimization.

Traditional shortest-path algorithms seek:

The optimum

K-shortest-path algorithms seek:

The best set of alternatives

This distinction appears frequently in real systems.

Users rarely want only one option.

They want choices.

Consequently, many practical optimization systems operate closer to K-shortest-path search than to pure shortest-path computation.

Complexity

The complexity depends heavily on the chosen algorithm.

Modified Dijkstra

Operation	Complexity
Priority queue operations	O(KE log(KV))
Memory usage	O(KV)

Yen's Algorithm

Operation	Complexity
K shortest simple paths	O(KV(E + V log V))

Eppstein's Algorithm

Operation	Complexity
Preprocessing	O(E + V log V)
Path generation	O(K log K)

The best choice depends on graph size and the value of K.

Common Mistakes

Do not assume the second shortest path differs substantially from the shortest path.

Do not confuse distinct paths with distinct distances.

Do not finalize vertices after a single visit.

Do not ignore path reconstruction requirements. Distances alone are often insufficient.

Do not use exhaustive path enumeration unless graphs are extremely small.

Practical Applications

K-shortest-path algorithms appear in:

GPS navigation
Airline route planning
Network failover routing
Supply-chain optimization
Workflow planning
Recommendation systems
Robotics
Telecommunications

Many systems require alternatives rather than a single optimum.

Takeaway

The K-shortest-path problem extends shortest-path computation from finding one optimal route to finding an ordered sequence of alternatives. By allowing multiple visits to vertices and preserving competing routes, these algorithms generate backup plans, alternative recommendations, and resilient routing strategies. The resulting techniques form a bridge between pure optimization and decision support, where multiple high-quality solutions are often more valuable than a single perfect one.