C++ 最短路总结 朴素Dijkstra算法 || 模版题，求最短路

算法选择：

稠密图用邻接矩阵写，稀疏图用邻接表写。

朴素dijkstra：

给定一个 n
个点 m
条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1
号点到 n
号点的最短距离，如果无法从 1
号点走到 n
号点，则输出 ?1
。

输入格式
第一行包含整数 n
和 m
。

接下来 m
行每行包含三个整数 x,y,z
，表示存在一条从点 x
到点 y
的有向边，边长为 z
。

输出格式
输出一个整数，表示 1
号点到 n
号点的最短距离。

如果路径不存在，则输出 ?1
。

数据范围
1≤n≤500
,
1≤m≤105
,
图中涉及边长均不超过10000。

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; //1号点的距离初始化成0
    
    for(int i = 0; i < n; i ++) //迭代n次，每次先找最小值，找到当前没有确定最短路长度的点中距离最小的那一个
    //这个循环就是在所有flase（也就是距离还没有确定的）中的点找到一个距离最短的点。
    {
        int t = -1; //表示还没有确定
        for(int j = 1; j <= n; j ++ ) //遍历所有点
            if(!st[j] && (t == -1 || dist[t] > dist[j])) //还没有确定最短路 并且 t==-1 或者当前的t不是最短的
                t = j; //t更新成j
        
        st[t] = true; //更新好了，标记一下
        
        for(int j = 1; j <= n; j ++ ) //遍历，拿t更新一下其他点的距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if(dist[n] == 0x3f3f3f3f) //说明1和n不连通
        return -1;
    return dist[n]; //返回最短距离
}

int main ()
{
    cin>>n>>m;
    
    memset(g, 0x3f, sizeof g);
    
    
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b], c);
    }
    int t = dijkstra();
    cout<<t<<endl;
    return 0;
}

在 Dijkstra 算法的实现中，t 变量用于记录当前阶段（迭代）中找到的未确定最短路径的点中距离起点最近的点。t 的初始化为 -1 是为了在第一次迭代时能够找到一个未确定最短路径的点，因为 -1 明显不是合法的点编号。

具体分析一下循环的逻辑：

第一次迭代： t 初始值为 -1，然后遍历所有点，找到第一个未确定最短路径的点 j，将 t 更新为 j。

后续迭代： 在后续的迭代中，如果有未确定最短路径的点，t 将被更新为其中距离起点最近的点。在每次迭代中，t 的值都会在当前未确定最短路径的点中选择距离最短的那个。如果 t 的初始值不是 -1，而是任意一个点的编号，可能会导致在第一次迭代时选择的起始点影响后续迭代的结果。

总之，通过将 t 初始化为 -1，可以确保每次迭代都能在未确定最短路径的点中选择距离起点最近的点，以获得正确的最短路径信息。