图的最短路径

Dijkstra 算法

​ 给定一个带权图以及其起点和终点，求起点到终点之间的最短路径。如下图所示，以A点为起点，F点为终点，求A到F的最短路径。

​ Dijkstra的算法思想是一种贪婪策略，算法贪婪地探索从s开始的路径，每次移动到下一个最近的节点，通过这种方式实际上构造了从s到图中每个其他节点的最短路径。即从上述最短距离数组中每次选择一个最近的点，将其作为下一个点，然后重新计算从起始点经过该点到其他所有点的距离，更新最短距离数据。已经选取过的点就是确定了最短路径的点，不再参与下一次计算。

​ 更加形式化的表达如下：

• 对于图 $G=(V,E,W),V={A,B,C,D,E,F},s=A,t=F$

• 初始化确定集合$K={s},Path(s)=\varnothing,d(s)=0$

• 对于所有不在K中的结点$i\in (V-K)$，计算距离$d(i) = min{d(u)+w(u,i)},u \in K$

• 选择$d(i)$中最小的值对应的结点，将其加入到K中，并修改不属于K的结点到K中结点的最小距离

const int infinity = 99999;

void dijkstra(vector<vector<int>> G, vector<int>& res){
    int points = G.size();
    vector<int> dist(points);
    vector<bool> flag(points,false);
    res = dist;
    // 起点 初始化被选集
    flag[0] = true;
    for(int i=0;i<points;++i){
        dist[i] = G[0][i];
    }
    // 寻找最短路径
    for(int i=1;i<points-1;++i){
        int min = infinity;
        int u = -1;
        for(int j=0;j<points;++j){
            // 比较离原点最近的点
            if(!flag[j]&&dist[j]<min){
                u = j;
                min = dist[j];
            }
        }
        // 找出最近点之后，更新最短距离
        flag[u] = true;
        for(int j=1;j<points;++j){
            if(!flag[j]&&(dist[u]+G[u][j]<dist[j])){
                dist[j] = dist[u] + G[u][j];
                res[j] = u;
            }
        }
    }
}

1631 最小体力消耗路径 (opens new window)

给定一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。

一开始在最左上角的格子 (0, 0) ，且希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。

每次可以往 上，下，左，右 四个方向之一移动，想要找到耗费体力最小的一条路径。

一条路径耗费的体力值是路径上相邻格子之间高度差绝对值的最大值决定的。

请返回从左上角走到右下角的最小体力消耗值 。

输入：heights = [[1,2,2],[3,8,2],[5,3,5]] 输出：2 解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

解析：