Introduction

The phrase "next-to-shortest path" sounds precise, but it often hides several different problems. Before you choose an algorithm, you need to know whether you want the second-best distance, the second distinct route, or the second simple path with no repeated vertices.

For many engineering tasks with non-negative edge weights, the most practical answer is a Dijkstra-style algorithm that keeps the best and second-best distances to each node. That is not the full answer for every graph-theory variant, but it is often the right starting point.

Define the Variant First

Different teams use "next-to-shortest" to mean different things:

• the second shortest distance from source to target
• the shortest path whose cost is strictly larger than the best path
• the second shortest simple path, where vertices cannot repeat
• the next different edge sequence, even if its total cost ties

Those definitions lead to different algorithms. A route-planning service may care about distinct paths. A coding interview may care only about the next larger cost. A research paper may assume simple paths and non-negative weights. If you skip this clarification, you can easily solve the wrong problem and still produce code that looks correct.

A Practical Two-Distance Dijkstra

If the graph has non-negative weights and you only need the best and second-best distances, keep two values for each node:

• 'best[v] is the shortest known distance to v'
• 'second[v] is the shortest known distance that is strictly larger than best[v]'

Each relaxation can improve best, or it can become the new second if it falls in between.

1import heapq
2from collections import defaultdict
3
4
5def second_shortest_distance(n, edges, src, dst):
6    graph = defaultdict(list)
7    for u, v, w in edges:
8        graph[u].append((v, w))
9
10    inf = 10**18
11    best = [inf] * n
12    second = [inf] * n
13    best[src] = 0
14
15    pq = [(0, src)]
16
17    while pq:
18        dist, node = heapq.heappop(pq)
19        if dist > second[node]:
20            continue
21
22        for nxt, weight in graph[node]:
23            cand = dist + weight
24
25            if cand < best[nxt]:
26                second[nxt] = best[nxt]
27                best[nxt] = cand
28                heapq.heappush(pq, (best[nxt], nxt))
29                if second[nxt] < inf:
30                    heapq.heappush(pq, (second[nxt], nxt))
31            elif best[nxt] < cand < second[nxt]:
32                second[nxt] = cand
33                heapq.heappush(pq, (second[nxt], nxt))
34
35    return best[dst], second[dst]
36
37
38edges = [
39    (0, 1, 1),
40    (0, 2, 2),
41    (1, 3, 3),
42    (2, 3, 2),
43    (1, 2, 1),
44]
45
46print(second_shortest_distance(4, edges, 0, 3))

This pattern is efficient, easy to test, and good enough for many routing, scheduling, and contest-style problems.

When This Is Not Enough

The two-distance trick does not fully solve every version of the problem. If your requirement is the second shortest simple path, repeated vertices may produce candidates that are legal for the distance-based method but illegal for your application.

That is when algorithms for k shortest simple paths become relevant. Yen's algorithm is a common practical choice if:

• the actual route sequence matters
• you need several alternatives, not just one backup route
• graph size is moderate enough that heavier logic is acceptable

There are also specialized results for formal next-to-shortest path problems on particular graph classes, especially undirected graphs with non-negative weights. The main lesson is that "second distance" and "second simple path" are not the same problem.

Unweighted Graphs

If every edge has unit cost, switch from Dijkstra to breadth-first search and track best and second-best hop counts:

1from collections import deque, defaultdict
2
3
4def second_shortest_hops(n, edges, src, dst):
5    graph = defaultdict(list)
6    for u, v in edges:
7        graph[u].append(v)
8        graph[v].append(u)
9
10    inf = 10**9
11    best = [inf] * n
12    second = [inf] * n
13    best[src] = 0
14
15    q = deque([(src, 0)])
16
17    while q:
18        node, dist = q.popleft()
19        for nxt in graph[node]:
20            cand = dist + 1
21            if cand < best[nxt]:
22                second[nxt] = best[nxt]
23                best[nxt] = cand
24                q.append((nxt, cand))
25            elif best[nxt] < cand < second[nxt]:
26                second[nxt] = cand
27                q.append((nxt, cand))
28
29    return best[dst], second[dst]

This is often enough for puzzle solvers, game-state graphs, and interview questions built on unweighted edges.

Common Pitfalls

The biggest mistake is implementing a second-shortest walk when the requirement was a second simple path.

Another common error is using Dijkstra-based logic even though the graph can contain negative edges. Once negative weights appear, the assumptions behind the algorithm break.

A third issue is failing to define tie behavior. If two different routes have the same total cost, do they count as separate answers or as one shortest result

Finally, some implementations return only the distance even though the caller needs the route itself. If the path must be reconstructed, store predecessor information as part of the state.

Summary

• Define exactly what "next-to-shortest" means before picking an algorithm.
• For non-negative weighted graphs, a two-distance Dijkstra is the most practical answer in many systems.
• Use BFS-based tracking for unweighted graphs.
• If you need simple paths or several alternatives, move toward Yen-style algorithms or specialized methods.
• Most failures come from requirement ambiguity, not from heap implementation details.