Dijkstra 算法

【基本思想】

Dijkstra 算法是贪心的蓝白点思想，其将点分为两类，一类是已确定最短路径的白点，一类是未确定最短路径的蓝点

求一个点的最短路径，就是把这个点由蓝点变为白点，从起点到蓝点的最短路径上的中转点在这个时刻只能是白点

初始时，将起点到终点的距离标记为 $0$，而后进行 $n$ 次循环，每次找出一个到起点距离 $dis[u]$ 最短的点 $u$ ，将它从蓝点变为白点，随后枚举所有白点 $v_i$，如果以此白点为中转到达蓝点 $v_i$ 的路径 $dis[u]+w[u][v_i]$ 更短的话，这将它作为 $v_i$ 的更短路径（此时还不能确定是不是 $v_i$ 的最短路径）

以此类推，每找到一个白点，就尝试用它修改其他所有蓝点，中转点先于终点变成白点，故每一个终点一定能被它的最后一个中转点所修改，从而求得最短路径

【算法分析】

以下图为例

算法开始时，作为起点的 dis[1]=0，其他的点 dis[i]=INF

第一轮循环找到 dis[1] 最小，将 $1$ 变为白点，对所有蓝点进行修改，使得：dis[2]=2，dis[3]=4，dis[4]=7

此时，dis[2]、dis[3]、dis[4] 被它的最后一个中转点 $1$ 修改了最短路径

第二轮循环找到 dis[2] 最小，将 $2$ 变成白点，对所有蓝点进行修改，使得：dis[3]=3、dis[5]=4

此时，dis[3]、dis[5] 被它的最后一个中转点 $2$ 修改了最短路径

第三轮循环找到 dis[3] 最小，将 $3$ 变成白点，对所有蓝点进行修改，使得：dis[4]=4

此时，dis[4] 被它的最后一个中转点 $3$ 修改了最短路径，但发现以 $3$ 为中转不能修改 $5$，说明 $3$ 不是 $5$ 的最后一个中转点

接下来两轮循环将 $4$、$5$ 也变成白点

循环结束，所有点的最短路径均可求出

【实现】

int dis[N];  //单源最短距离
int G[N][N]; //邻接矩阵
bool vis[N]; //表示dis[i]是否已经计算完
void dijkstra(int n, int s) { //简化版，不可处理重边
    for (int i = 1; i <= n; i++) {
        int x;             //x标记当前最短距离的点
        int min_dis = INF; //记录当前最小距离

        for (int y = 1; y <= n; y++) {
            if (!vis[y] && min_dis >= dis[y]) {
                x = y;
                min_dis = dis[x];
            }
        }

        vis[x] = true;

        for (int y = 1; y <= n; y++)
            dis[y] = min(dis[y], dis[x] + G[x][y]);
    }
}
int main() {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));

    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y, dis;
        scanf("%d%d%d", &x, &y, &dis);
        G[x][y] = dis;
        G[y][x] = dis;
    }
    
    int start;
    scanf("%d", &start);
    dijkstra(n, start);
    for (int i = 1; i <= n; i++)
        printf("%d\n", dis[i]);
    
    return 0;
}