单源最短路径 – dijkstra

最短路径是图论中的经典问题即：给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。 dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。 Notes：

• 1 dijkstra算法可以求的初始节点到其他全部节点的最短路径。
• 2 权值不能为负

Dijkstra算法原理为贪心思想，即每次都寻找离源点最近且未访问过的节点。 Dijkstra算法和Prim算法思想基本一致，只是细微之处有不同：

• 1 Dijkstra算法是找找离源点最近且未访问过的节点，Prim算法是找离最小生成树最近且未访问过的节点。
• 2 Dijkstra算法的minDist数组是指节点j离源点最近的距离。Prim算法的minDist数组是指节点j离最小生成树最近的距离。

以下为代码随想录的模拟过程： 初始状态： 选择节点1，将visited[i]=true, 更新minDist. 选择节点2，将visited[2]=true, 更新minDist. 选择节点3，将visited[3]=true, 更新minDist. 选择节点4，将visited[4]=true, 更新minDist. 选择节点6，将visited[6]=true, 更新minDist. 选择节点5，将visited[5]=true, 更新minDist. 选择节点7，将visited[7]=true, 更新minDist. 最终源节点1到终止节点7的路径为： 模拟结束，我们来道真题来操练一下。 代码如下：

#include 
#include 
#include 
using namespace std;

int main(){
    int N, M;
    int S, E, V;
    cin >> N >> M;
    vector> edges(N+1, vector(N+1, INT_MAX));
    while(M--){
        cin >> S >> E >> V;
        edges[S][E] = V;
    }
    
    // prim必备数组
    vector minDist(N+1, INT_MAX);
    vector isInTree(N+1, false);
    minDist[1] = 0;  // 第一个元素的值设置为0，用于步骤3更新minDist数组
    for(int i=1; i<=N; i++){
        // 1 找离源节点最近的未访问节点
        int cur = 1;  // 从第一个元素开始
        int minValue = INT_MAX;
        for(int j=1; j<=N; j++){
            if (!isInTree[j] && minValue>minDist[j]){
                cur = j;
                minValue = minDist[j];
            }
        }
        // 2 将未访问节点设置为访问
        isInTree[cur] = true;
        // 3 更新minDist数组
        for(int j=1; j<=N; j++){
            if (!isInTree[j] && edges[cur][j] != INT_MAX && (minDist[cur] + edges[cur][j]) < minDist[j]){
                minDist[j] = minDist[cur] + edges[cur][j];
            }
        }
    }

    if (minDist[N] == INT_MAX) cout << -1 << endl;
    else cout << minDist[N] << endl;
    return 0;
}