如何在Minimum Path Sum问题中实现最小和路径的查找与打印（Python）

给定一个m×n的非负整数网格，找出一条从左上角到右下角的路径，使得路径上所有数字的和最小。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：路径1 → 3 → 1 → 1 → 1的和最小。

问题 #

能否用Python打印出这条1 → 3 → 1 → 1 → 1的路径？

现状 #

能计算最小路径和，但无法打印路径。尝试用BFS实现，但解决方案未考虑路径权重（即路径和），代码如下：

def bfs(grid):
    queue = collections.deque([[(0,0)]])
    seen = set([(0,0)])
    while queue:
        path = queue.popleft()
        x, y = path[-1]
        if (x,y) == (width-1, height-1):
            return path
        for x2, y2 in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)):
            if 0 <= x2 < width and 0 <= y2 < height and (x2, y2) not in seen:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2))

解决方案 #

你原来的BFS只关注路径步数，没考虑路径和的权重，所以无法找到最小和路径。下面提供两种可行的实现方式：

方法一：动态规划+回溯记录路径

通过动态规划记录每个位置的最小路径和，同时记录该位置的前驱坐标，最后从终点回溯到起点得到路径。

def min_path_sum_with_path(grid):
    m = len(grid)
    n = len(grid[0]) if m > 0 else 0
    if m == 0 or n == 0:
        return []
    
    # dp[i][j]存储到达(i,j)的最小路径和，prev[i][j]存储前驱坐标
    dp = [[0]*n for _ in range(m)]
    prev = [[None]*n for _ in range(m)]
    
    dp[0][0] = grid[0][0]
    # 填充第一行
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
        prev[0][j] = (0, j-1)
    # 填充第一列
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
        prev[i][0] = (i-1, 0)
    # 填充其他区域
    for i in range(1, m):
        for j in range(1, n):
            if dp[i-1][j] < dp[i][j-1]:
                dp[i][j] = dp[i-1][j] + grid[i][j]
                prev[i][j] = (i-1, j)
            else:
                dp[i][j] = dp[i][j-1] + grid[i][j]
                prev[i][j] = (i, j-1)
    
    # 从终点回溯路径
    path = []
    current = (m-1, n-1)
    while current is not None:
        path.append(grid[current[0]][current[1]])
        current = prev[current[0]][current[1]]
    # 反转得到从起点到终点的顺序
    path.reverse()
    return path

# 测试
grid = [[1,3,1],[1,5,1],[4,2,1]]
path = min_path_sum_with_path(grid)
print(" → ".join(map(str, path)))  # 输出：1 → 3 → 1 → 1 → 1

方法二：Dijkstra算法（带权重的优先队列）

利用优先队列每次弹出当前路径和最小的节点，直到到达终点，适合非负权重的网格场景。

import heapq

def min_path_sum_dijkstra(grid):
    m = len(grid)
    n = len(grid[0]) if m > 0 else 0
    if m == 0 or n == 0:
        return []
    
    # 优先队列元素：(当前路径和, x坐标, y坐标, 当前路径列表)
    heap = []
    heapq.heappush(heap, (grid[0][0], 0, 0, [grid[0][0]]))
    # 记录每个位置的最小路径和，避免重复处理
    min_sum = [[float('inf')]*n for _ in range(m)]
    min_sum[0][0] = grid[0][0]
    
    # 仅考虑向右、向下移动（向上/向左会增加路径长度，不可能得到最小和）
    directions = [(1,0), (0,1)]
    while heap:
        current_sum, x, y, path = heapq.heappop(heap)
        if x == m-1 and y == n-1:
            return path
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n:
                new_sum = current_sum + grid[nx][ny]
                if new_sum < min_sum[nx][ny]:
                    min_sum[nx][ny] = new_sum
                    heapq.heappush(heap, (new_sum, nx, ny, path + [grid[nx][ny]]))
    return []

# 测试
grid = [[1,3,1],[1,5,1],[4,2,1]]
path = min_path_sum_dijkstra(grid)
print(" → ".join(map(str, path)))  # 输出：1 → 3 → 1 → 1 → 1

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