这个 Dijkstra 代码如何 return 最小值（而不是最大值）？

Question

我正在 LeetCode.com 上解决这个问题 Path With Minimum Effort:

You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). Aim is to go from top left to bottom right. You can move up, down, left, or right, and you wish to find a route that requires the minimum effort. A route's effort is the maximum absolute difference in heights between two consecutive cells of the route. Return the minimum effort required to travel from the top-left cell to the bottom-right cell. For e.g., if heights = [[1,2,2],[3,8,2],[5,3,5]], the answer is 2 (in green).

我的密码是：

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];
    }
};

这被接受了，但我有两个问题：

一个。由于我们更新 dist[u][v] 如果它大于比 max(curr_cost,wt)，它如何保证最终我们 return 最小值 需要努力吗？也就是说，我们为什么不结束 return 上面红色部分的努力？

b。一些解决方案，例如 this one、短路和当我们第一次到达右下角（即 if(r==rows-1 and c==cols-1) return wt;）时立即 return - 这是如何工作的？以后再再访问右下角的节点时，能不能得到更短的dist？

Answer 1

问题陈述要求我们找到具有最小“努力”的路径。
“努力”定义为路径上相邻单元格之间的最大高度差。

表达式 max(curr_cost, wt) 处理问题陈述的 maximum 部分。从一个单元格移动到另一个单元格时，到新单元格的距离与到旧单元格的距离相同，或者是高度差，以较大者为准。因此 max(difference_in_heights, distance_to_old_cell).

而 Dijkstra 的算法处理了问题陈述的 minimum 部分，我们不是使用与起始节点的距离，而是使用需要的“努力”从起始节点到任何给定节点。 Dijkstra 尝试最小化距离，因此它最小化了工作量。

Dijkstra 有两个密切相关的概念：visited 和 explored。当使用任何传入边到达节点时，节点是 visited。当一个节点的出边被用来访问它的邻居时，它就是 explored。 Dijkstra 的关键设计特征是在一个节点被探索之后，对该节点的额外访问永远不会增加到该节点的距离。这就是优先队列的原因。优先级队列保证被探索的节点具有任何未探索节点的最小距离。

在示例网格中，红色路径将在绿色路径之前被探索，因为红色路径在最后一步之前的努力为 1，而绿色路径的努力为 2。因此红色路径会将距离设置为右下单元格为 3，即 dist[2][2] = 3.

但是当探索绿色路径时，我们到达行=2，列=1 处的 3，我们有

距离[2][2] = 3
curr_cost=2
重量=2

所以 dist[2][2] > max(curr_cost, wt)，并且 dist[2][2] 减少到 2。

问题的答案：

一个。红色路径确实将右下角的单元格暂时设置为 3 的距离。但是红色路径的结果被丢弃，取而代之的是绿色路径的结果。这是Dijkstra算法求最小值的自然结果。

b。当右下角的节点准备好被探索时，即它位于优先队列的头部，那么它就有了最好的距离，所以算法可以在那个点停止.这也是 Dijkstra 算法的自然结果。优先级队列保证在一个节点被探索之后，以后访问该节点不会减少它的距离。

这个 Dijkstra 代码如何 return 最小值（而不是最大值）？

How does this Dijkstra code return minimum value (and not maximum)?

c++

algorithm

graph

dijkstra

graph-traversal