标签：最短路

概要

Dijkstra 算法是最常用的求最短路径的算法之一，它同时适用于有向图或无向图。
我们用 w[u][v] 来存储节点 u 到节点 v 的距离（或理解为这条边的权重）。将除源 S 以外的节点分成已标记和未标记的两部分，先更新一次源 S 到相邻节点的距离，然后通过 BFS（广度优先搜索）来遍历所有与未标记的与源 S 间接相连的节点并不断维护从源 S 到 i点的距离 dis[i]，最终得到最短路径。这个版本的 Dijkstra 最短路径算法的复杂度约为 O(N^2)。

输入

• 第 1 行 节点个数 n，边个数 m
• 第 2~m+1行 边起点 ui，边终点 vi，边权重 w[u][v]

实现

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <cstring>
#define offline
//#include <regex>
#define INF 2147483647
using namespace std;
int main()
{
    //srand((unsigned int)(time(NULL)));
    freopen("Dijkstra.in","r",stdin);
    int n, m, u;//n points,m threads, u as temp source
    scanf("%d%d", &n, &m);
    int w[n][n], d[n];

    bool sign[n];
    memset(sign,0,sizeof(sign));
    sign[0] = 1;
    
    d[0] = 0;
    for (int i = 0; i < n; i++)
        d[i] = INF;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            i == j ? w[i][j] = 0: w[i][j] = INF;

    int t1, t2, t3;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &t1, &t2, &t3);
        w[t1][t2] = t3;
        w[t2][t1] = t3;//only for non-direction map
    }
    //initial for d
    for (int i = 0; i < n; i++)
        d[i] = w[0][i];
    
    
    int min;
    for (int i = 0; i < n; i++)
    {
        min = INF;
        for (int j = 0; j < n; j++)
        {
            if (sign[j] == 0 && d[j] < min)
            {
                min = d[j];
                u = j;
            }
            
        }
        sign[u] = 1;
        for (int v = 0; v < n; v++)
        {
            if ((d[v] > d[u] + w[u][v]) && w[u][v] < INF){
                #ifdef offline
                printf("updated d[%d] from %d to %d\n", v,d[v],d[u]+w[u][v]);
                #endif
                d[v] = d[u] + w[u][v];
            }
        }
    }   
    for (int i = 0; i < n; i++)
        printf("dis[%d] %d\n", i, d[i]);
    return 0;
}