为什么该Dijkstra实现返回最小体力消耗而非最大值？

给定大小为rows x columns的二维数组heights，其中heights[row][col]表示单元格(row, col)的高度，目标是从左上角走到右下角。你可以向上下左右四个方向移动，要求找到所需体力消耗最小的路径。路径的体力消耗定义为路径上相邻单元格高度差绝对值的最大值，请返回从左上角到右下角所需的最小体力消耗。例如，当heights = [[1,2,2],[3,8,2],[5,3,5]]时，答案为2（图中绿色路径）。

实现代码 #

class Solution {
public:
    vector<pair<int,int>> getNeighbors(vector<vector<int>>& h, int r, int c) {
        vector<pair<int,int>> n;
        if(r+1<h.size()) n.push_back({r+1,c});
        if(c+1<h[0].size()) n.push_back({r,c+1});
        if(r-1>=0) n.push_back({r-1,c});
        if(c-1>=0) n.push_back({r,c-1});
        return n;
    }
    
    int minimumEffortPath(vector<vector<int>>& heights) {
        int rows=heights.size(), cols=heights[0].size();
        
        using arr=array<int, 3>;
        priority_queue<arr, vector<arr>, greater<arr>> pq;
        vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
        pq.push({0,0,0});    //r,c,weight
        dist[0][0]=0;
        
        //Dijkstra
        while(pq.size()) {
            auto [r,c,wt]=pq.top();
            pq.pop();
            
            if(wt>dist[r][c]) continue;
            
            vector<pair<int,int>> neighbors=getNeighbors(heights, r, c);
            for(auto n: neighbors) {
                int u=n.first, v=n.second;
                int curr_cost=abs(heights[u][v]-heights[r][c]);
                if(dist[u][v]>max(curr_cost,wt)) {
                    dist[u][v]=max(curr_cost,wt);
                    pq.push({u,v,dist[u][v]});
                }
            }
        }
        
        return dist[rows-1][cols-1];
    }
};

疑问解答 #

问题a：为什么仅当dist[u][v]大于max(curr_cost,wt)时更新的逻辑能保证返回最小体力消耗？ #

我们这里是对Dijkstra算法做了适配，核心逻辑和求单源最短路径完全一致：

• 我们把「到达某个单元格的最小体力消耗」类比为最短路径的长度，两个相邻单元格移动的边权就是二者高度差的绝对值，整条路径的总权值是路径上所有边权的最大值。
• 这种权值计算规则满足Dijkstra算法的适用前提：路径权值非负，且延长路径时总权值不会减小。dist数组存储的是到达每个单元格当前已知的最小体力消耗，只有当新路径计算得到的最大高度差比已有的dist[u][v]更小的时候，才会更新dist并将该状态加入优先队列，这保证了dist数组里存储的始终是到对应点的最小可能值。
• 消耗更大的非最优路径（比如示例中的红色路径），它的权值会比最优路径大，在小顶堆的优先队列里会排在更靠后的位置。当最优路径对应的dist已经更新完成后，后续非最优路径的状态弹出时，判断到wt > dist[r][c]就会直接跳过，不会影响最终结果。

问题b：为什么第一次弹出右下角节点时可以直接返回结果，不会有更小的消耗？ #

这个逻辑是小顶堆实现的Dijkstra算法的固有性质：

• 优先队列是按路径消耗从小到大排序的，每次从堆顶弹出的都是当前所有待处理状态里路径消耗最小的那个。
• 当右下角节点第一次被弹出时，就意味着我们已经找到了到达它的最小体力消耗：因为所有边权都是非负的，后续可能到达右下角的路径，消耗都只会比当前弹出的这个值更大，不可能出现更小的情况。
• 所以不需要等到整个队列处理完，第一次弹出右下角节点时直接返回即可，后续再访问到右下角节点时，对应的消耗肯定都大于等于当前的最小值，不会有更优解。

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