(资料图片仅供参考)

最短路单源最短路求从一个点到其他所有点的最短距离所有边权是正数朴素Dijkstra算法 O(n^2)用于稠密图 m >= n步骤：dist[i]：每个点离起点的距离S：已经确定最短距离的点V：没有确定最短距离的点初始化所有点的距离dist[起点] = 0；dist[其他点] = inf循环找V中离起点最近的点t将t放入S中用t的距离更新其他点的距离代码：

const int N = 510;int g[N][N];//稠密图用邻接矩阵int dist[N];//到原点的距离int st[N];//标记数组int dijkstra(){//初始化距离memset(d, 0x3f, sizeof d);d[1] = 0;//遍历n次每次找距离原点最近的节点for(int i = 1; i <= n; ++ i){//在n个接节点中找int t = 0;for(int j = 1; j <= n; ++ j)if(!st[j] && (!t || d[t] > d[j])t = j; //找到了}st[t] = 1; //标记已经找到最短距离//更新所有节点的距离for(int j = 1; j <= n; ++ j)d[j] = min(d[j], d[t] + g[t][j]);if(d[n] == 0x3f3f3f3f) return -1;//1-n不连通else return d[n]; //返回1-n的最短距离}//注意初始化边权为infmemset(g, 0x3f, sizeof g);//输入边权while(m -- ){int a, b, c;cin >> a >> b >> c;//有重边就取最小边权g[a][b] = min(g[a][b], c);

堆优化Dijkstra算法 O(mlogn)用于稀疏图 m <= n用堆存储每个节点的距离，堆顶元素就是离原点距离最近的节点代码：

const int N = 1.5e5 + 10;typedef pair PII;int st[N];int h[N], e[N], ne[N], idx = 1;int d[N], w[N];//w[i]边i的权值int n, m;void add(int x, int y, int z){    e[idx] = y;    ne[idx] = h[x];    h[x] = idx;    w[idx] = z;    idx ++ ;}int dijkstra(){    //初始化    memset(d, 0x3f, sizeof d);    d[1] = 0;        priority_queue, greater > q;//小根堆        q.push({0, 1});//起点入堆        while(q.size()){        auto t = q.top();//取堆顶元素，离起点最近的节点        q.pop();                int dist = t.first, node = t.second;//获取信息                if(st[node]) continue;//已经求出最短距离就跳过        st[node] = 1;                for(int i = h[node]; i; i = ne[i]){            int j = e[i];//遍历相连的所有节点            if(d[j] > dist + w[i]){//更新最短距离                d[j] = dist + w[i];                q.push({d[j], j});//入堆            }                        }    }        if(d[n] == 0x3f3f3f3f) return -1;    else return d[n];}

存在边权是负数Bellman-Ford算法 O(nm)能够找到有边数限制的最短路径可以判断图中有无负权回路当外层循环执行n次（最短路更新了n次），说明最大有n条边构成了最短路，即有n+1个节点构成了最短路，根据鸽巢原理知，路中必有两个相同的节点，即路中有回路，又最短路更新的前提是最短路可以变得更小，所以该回路一定构成负权回路当有边数限制时，即使图中有负环也无所谓，因为负环不能被无限选择代码：

const int N = 510;const int M = 1e4 + 10;struct egde{ //边int u, v, w;}edges[M];int d[N], backup[N];//备份数组int n, m, k;int ballmen_ford(){//初始化memset(d, 0x3f, sizeof d);d[1] = 0;for(int i = 1; i <= k; ++ i){ //k条边限制memcpy(backup, d, sizeof d); //存备份for(int j = 1; j <= m; ++ j){ //遍历每一条边int u = edges[j].u; //获取信息int v = edges[j].v;int w = edges[j].w;d[v] = min(d[v], backup[u] + w); //利用备份更新}}if(d[n] > 0x3f3f3f3f / 2) return -N;else return d[n];}int main(){cin >> n >> m >> k;for(int i = 1; i <= m; ++ i){int x, y, z;cin >> x >> y >> z;edges[i] = {x, y, z};}int t = ballmen_ford();if(t == -N) cout << "impossible";else cout << t << endl;return 0;}

SPFA算法 一般O(m)最坏O(nm)相当于优化版的ballmen_ford可以用于判断图中是否有负权回路设置cnt[i]数组，表示最短路从起点到i的边的数量，当某时刻边的数量>=n，说明路中有回路代码：

const int N = 1e5 + 10;int h[N], e[N], ne[N], idx = 1;int d[N], w[N], cnt[N];//cnt[i]数组表示从起点到i的最短路中的边的数量int st[N]; //标记元素是否已经进入队列int n, m;void add(int a, int b, int z){    e[idx] = b;    ne[idx] = h[a];    h[a] = idx;    w[idx] = z;    idx ++ ;}bool spfa(){    queue q;    for(int i = 1; i <= n; ++ i){//所有节点入队，负环有可能不是从1-n路径上的，所以以每个节点为起点的路径都要检查        q.push(i);        st[i] = 1;//标记已入队    }        while(q.size()){        int t = q.front();        q.pop();        st[t] = 0;//出队        for(int i = h[t]; i; i = ne[i]){            int j = e[i];            if(d[j] > d[t] + w[i]){                d[j] = d[t] + w[i]; //更新                cnt[j] = cnt[t] + 1;//边数加一                if(cnt[j] >= n) return true;//边数>=n时，说明有环                if(!st[j]){                    q.push(j);//只将更新过的元素入队                    st[j] = 1;                }            }        }    }    return false;}int main(){    cin >> n >> m;    while(m -- ){        int x, y, z;        cin >> x >> y >> z;        add(x, y, z);    }        if(spfa()) cout << "Yes";    else cout << "No";    return 0;}

d[v] = min(d[v], backup[u] + w); //利用备份更新，这句话存在很多无效更新。只有当u更新过后，d[v]的更新才有效，因此只需要将更新过的节点放入一个集合，每次只用在集合中取元素去更新它邻接的节点有些正权图也可以用SPFA算法代码：

const int N = 1e5 + 10;int h[N], e[N], ne[N], idx = 1;int d[N], w[N];int st[N]; //标记元素是否已经进入队列int n, m;void add(int a, int b, int z){    e[idx] = b;    ne[idx] = h[a];    h[a] = idx;    w[idx] = z;    idx ++ ;}int spfa(){//初始化    memset(d, 0x3f, sizeof d);    d[1] = 0;    //队列存储更新过距离的节点    queue q;    q.push(1);    st[1] = 1;//标记已入队        while(q.size()){//循环        int t = q.front();        q.pop();        st[t] = 0;        for(int i = h[t]; i; i = ne[i]){            int j = e[i];            if(d[j] > d[t] + w[i]){                d[j] = d[t] + w[i]; //更新                if(!st[j]){                    q.push(j);//只将更新过的元素入队                    st[j] = 1;                }            }        }    }    if(d[n] > 0x3f3f3f3f / 2) return -N;    else return d[n];}int main(){    cin >> n >> m;    while(m -- ){        int x, y, z;        cin >> x >> y >> z;        add(x, y, z);    }        int t = spfa();    if(t == -N) cout << "impossible";    else cout << t;    return 0;}

存在负权边的图中存在最短路的话，图中一定不能有负权回路，除非最短路边数有限制，否则一直沿着回路绕，路径越来越小，直到最短路为负无穷多源汇最短路源点起点，汇点终点，起点与终点任意选取Floyd算法 O(n^3)可以处理有负权的图，但不能处理有负权回路的图代码：

const int N = 210;const int M = 2e4 + 10;const int INF = 0x3f3f3f3f;int d[N][N];//存储两点间的最短路int n, m, k;void floyd(){//基于动态规划    for(int k = 1; k <= n; ++ k)        for(int i = 1; i <= n; ++ i)            for(int j = 1; j <= n; ++ j)                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}int main(){    cin >> n >> m >> k;    //初始化    for(int i = 1; i <= n; ++ i)        for(int j = 1;j <= n; ++ j)            if(i == j) d[i][j] = 0; //去自环            else d[i][j] = INF;        while(m -- ){        int x, y, z;        cin >> x >> y >> z;        d[x][y] = min(d[x][y], z);//去重边    }        floyd();        while(k -- ){        int u, v;        cin >> u >> v;        int t = d[u][v];        if(t > INF / 2) cout << "impossible" << endl;        else cout << t << endl;    }    return 0;}