如何在Python的Dijkstra算法实现中输出实际最短路径？

我是Advent of Code解题者，已用Python实现BFS算法（原描述提到Dijkstra，实际代码为BFS），成功计算出到达字符"E"的步数，示例数据结果为31。但首次使用这类算法，不清楚如何输出组成最短路径的坐标序列，现寻求解决方案。

输入数据 #

Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi

现有代码 #

#!/usr/bin/env python3
from collections import deque

data = [line for line in open(0).read().splitlines()]
m = {"S": "a", "E": "z"}

E = 0 + 0j
S = 0 + 0j
co = {}

for y, d in enumerate(data):
    for x, i in enumerate(d):
        if i == "E":
            E = x + y*1j
        if i == "S":
            S = x + y*1j
        co[(x + y*1j)] = [m.get(i, i), ord(m.get(i, i))]


def dfs(grid, start, end):
    buffer = deque([(start, 0)])
    seen = set()

    while buffer:
        current = buffer.popleft()
        if current[0] in seen:
            continue

        # Part 1
        if current[0] == end:
            return current[1], seen, len(seen)

        seen.add(current[0])

        neighbours = [
            current[0] + (-1 + 0j),
            current[0] + (1 + 0j),
            current[0] + (0 + -1j),
            current[0] + (0 + 1j)
        ]
        for n in neighbours:
            if n.real < 0 or n.imag < 0 or n.real >= len(data[0]) or n.imag >= len(data):
                #print(n)
                continue
            if grid[n][1] <= grid[current[0]][1] + 1:

                buffer.append((n, current[1]+1))
    return False

print(dfs(co, S, E)[0])

解决方案：记录并回溯路径 #

要输出最短路径，核心是在BFS过程中记录每个节点的前驱节点（即从哪个节点走到当前节点），到达终点后从终点反向回溯至起点，再反转得到正序路径。

修改后的代码如下：

#!/usr/bin/env python3
from collections import deque

data = [line for line in open(0).read().splitlines()]
m = {"S": "a", "E": "z"}

E = 0 + 0j
S = 0 + 0j
co = {}

for y, d in enumerate(data):
    for x, i in enumerate(d):
        if i == "E":
            E = x + y*1j
        if i == "S":
            S = x + y*1j
        co[(x + y*1j)] = [m.get(i, i), ord(m.get(i, i))]


def bfs_with_path(grid, start, end):
    buffer = deque([start])
    seen = set([start])
    prev = {}  # 记录每个节点的前驱节点

    while buffer:
        current = buffer.popleft()

        # 到达终点，回溯路径
        if current == end:
            path = []
            while current in prev:
                path.append(current)
                current = prev[current]
            path.append(start)  # 加入起点
            path.reverse()  # 反转得到正序路径
            return len(path)-1, path  # 返回步数（路径长度-1）和路径

        neighbours = [
            current + (-1 + 0j),
            current + (1 + 0j),
            current + (0 + -1j),
            current + (0 + 1j)
        ]
        for n in neighbours:
            if n.real < 0 or n.imag < 0 or n.real >= len(data[0]) or n.imag >= len(data):
                continue
            if n not in seen and grid[n][1] <= grid[current][1] + 1:
                seen.add(n)
                prev[n] = current
                buffer.append(n)
    return False, []

steps, path = bfs_with_path(co, S, E)
print(f"最短步数：{steps}")
print("最短路径坐标：")
for coord in path:
    print(f"({int(coord.real)}, {int(coord.imag)})")

关键修改点说明： #

1. 新增prev字典：用于存储每个节点的前驱，比如prev[n] = current表示节点n是从current走过来的。
2. 调整BFS逻辑：将队列元素简化为节点（步数可通过路径长度推导），仅当节点未被访问过时才记录前驱并加入队列。
3. 终点回溯路径：到达终点后，从end开始遍历prev字典，直到起点，再反转得到从起点到终点的正序路径。

运行修改后的代码，示例数据会输出步数31，以及包含32个坐标的路径（步数=路径长度-1），符合问题要求。

内容的提问来源于stack exchange，提问作者user2156115