基于DFS在四向加权网格中求解最短与最长路径距离的问题

你已经实现了加权网格中从(0,0)到右下角的最短路径DFS解法，但修改代码求最长路径时遇到了问题——直接替换Infinity为-Infinity并反转判断条件会导致逻辑失效，因为最长路径的特性和最短路径完全不同，下面具体分析并给出解决思路：

为什么直接修改最短路径代码行不通？ #

最短路径的DFS解法利用了最优子结构：一旦某个节点的最短距离被确定，后续再找到更长的路径到该节点时，无需再处理（因为不可能得到更短的路径）。但最长路径没有这个特性——即使已经找到一条到某个节点的路径，后续可能存在绕路但总长度更大的路径，所以直接用distance矩阵判断是否更新的逻辑会失效，甚至因为不断更新导致无限递归。

另外，网格支持四向遍历，若不严格控制访问标记，很容易陷入循环遍历同一个节点的情况。

最长路径的DFS解决思路 #

最长路径需要遍历所有可能的合法路径，记录到达终点时的最大路径总长度。具体步骤：

• 维护一个变量记录当前找到的最长路径距离
• 遍历过程中标记当前节点为已访问，避免循环
• 每次到达右下角终点时，计算当前路径的总长度，更新最长距离
• 回溯时恢复节点的原始值，确保其他路径可以正常访问该节点

修改后的代码实现 #

var grid = [
  [1, 3, 1],
  [3, 3, 3],
  [3, 3, 2]
];

let directions = [[-1,0], [1, 0], [0,-1], [0,1]];
let ROWS = grid.length;
let COLS = grid[0].length;
let maxDistance = -Infinity;

// 初始路径长度是起点的权重
dfs(0, 0, grid[0][0]);

console.log(maxDistance);

function dfs(row, col, currentTotal) {
    // 到达终点，更新最长距离
    if (row === ROWS - 1 && col === COLS - 1) {
        maxDistance = Math.max(maxDistance, currentTotal);
        return;
    }

    let currentValue = grid[row][col];
    grid[row][col] = -1; // 标记为已访问

    for (let dir of directions) {
        let [dx, dy] = dir;
        let newRow = row + dx;
        let newCol = col + dy;

        // 边界检查 + 未访问检查
        if (newRow >= 0 && newRow < ROWS && newCol >= 0 && newCol < COLS && grid[newRow][newCol] !== -1) {
            // 递归时累加下一个节点的权重
            dfs(newRow, newCol, currentTotal + grid[newRow][newCol]);
        }
    }

    grid[row][col] = currentValue; // 回溯，恢复节点值
}

代码说明 #

• 去掉了原来的costMatrix，改用currentTotal参数传递当前路径的总长度，能准确追踪每条路径的累计权重
• 当到达终点时，直接比较并更新maxDistance
• 访问标记仅在当前路径的递归过程中生效，回溯时恢复，保证其他路径可以重新访问该节点
• 这种方式会遍历所有可能的合法路径，因此在网格较大时效率会很低，但完全符合你用DFS实现的需求

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