单源最短路

单位权图的最短路问题：

直接 BFS ，时间复杂度 O（n+m）。

单源最短路问题：

只有 1 个起点。

迪杰斯特拉算法（dijkstra）

算法流程：
1. 设 dist[i] 表示起点 s 到 i 点的最短路径长度。 初始化 dist[s]=0 ,其余节点的 dist 值全部为正
无穷大；
2. 找出一个未被标记的、 dist[x] 最小的节点，去标记节点 x ；
3. 扫描节点 x 的所有出边 (x,y,z),若 dist[y]>dist[x]+z ，则使用 dist[x]+z 去更新 dist[y] ；
4. 重复步骤 2~3，直到所有节点都被标记了。

dijkstra 算法的正确性证明：

dijkstra 算法基于贪心思想，只能用于所有边的长度都是非负整数的图。因为当边权值都是非负数时，
全局最小值 dist[x] 不可能再被其他的节点所更新了（当前其他的点都比它的 dist 值大）。所以我们不断的选择全局最小值进行标记和扩展，最终可以得到起点 s 到每个节点的最短路径长度。

为什么边权不能有负数？

因为取出的全局最小值，我们会标记上这个点。但是可能存在一条负权使得全局最小值还可以更小，但是因为被标记了，导致无法再更新它了。

例题1：【模板】单源最短路径（弱化版）

时间复杂度：O(n²+m)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e4+10;
const int maxm = 5e5+10;
const LL INF = (1LL<<31)-1;
int head[maxm], vis[maxn];
LL dix[maxn];
int n, m, s, tot=0;
struct node
{
    int to, nxt, d;
}edge[maxm];
void add(int x, int y, int z)
{
    edge[tot].to = y;
        edge[tot].d = z;
    edge[tot].nxt = head[x];
    head[x] = tot++;
}
void dijkstra()
{
    for(int i=1; i<=n; ++i) // 初始化
        dix[i] = INF;
        dix[s] = 0;
        memset(vis, 0 ,sizeof(vis));
        for(int i=1; i<=n; ++i) //每一次标记1个点，所以跑n边循环
        {
            int x = 0;
            for(int j=1; j<=n; ++j) { // 找 未被标记全局最小值
            if(!vis[j] && (x==0 || dix[j]<dix[x]))
            x = j;
        }
        vis[x] = 1; // 标记全局最小值
        for(int j=head[x]; j!=-1;j=edge[j].nxt) // 枚举x点的出边
        {
            int v = edge[j].to;
            dix[v] = min(dix[v], 1LL *edge[j].d + dix[x]); // 更新 x 的对点
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    memset(head, -1, sizeof(head));
    while(m--)
    {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    add(x, y, z);
    }
    dijkstra();
    for(int i=1; i<n; ++i)
        printf("%lld ", dix[i]);
    printf("%lld\n", dix[n]);
    return 0;
}

堆优化 dijkstra 算法
我们可以发现 dijkstra 算法的瓶颈在于每次都要寻找全局最小值 dist[x] ，所以我们可以用一个小根堆对 dist[] 数组进行维护。

那么就可以用 O(log n) 的时间从堆中找出最小值，并且把它从堆中删除。整体时间复杂度变成 O(m*log n) 。

例题2：【模板】单源最短路径（标准版）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const int maxm = 2e5+10;
const int INF = (1<<31)-1;
int head[maxm], vis[maxn];
LL dix[maxn];
int n, m, s, tot=0;
struct node
{
    int to, nxt, d;
}edge[maxm];
struct Point // 自定义一个小根堆
{
    int dd, p; // dd表示 p点到起点的距离
    bool operator <(const Point &x) const {
    return dd > x.dd;
    }
} ;
void add(int x, int y, int z)
{
    edge[tot].to = y;
    edge[tot].d = z;
    edge[tot].nxt = head[x];
    head[x] = tot++;
}
void dijkstra()
{
    for(int i=1; i<=n; ++i)
        dix[i] = INF;
    memset(vis, 0 ,sizeof(vis));
    dix[s] = 0;
    priority_queue<Point> que;
    Point a;
    a.dd = 0; a.p = s; // 起点
    que.push(a); // 把起点放入小根堆中
    while(que.size())
    {
        //取出堆顶元素，也就是全局最小的 dix
        a = que.top(); que.pop();
        int x = a.p;
        if(vis[x]) continue;
        vis[x] = 1;
        //扫描 x 所有的出边
        for(int i=head[x]; i!=-1; i=edge[i].nxt)
        {
            int y = edge[i].to;
            if(dix[y] > dix[x] + 1LL*edge[i].d) { // 当对点 y 可以被更新的时候
                dix[y] = dix[x] + 1LL * edge[i].d;
                a.dd = dix[y]; a.p = y;
                que.push(a);
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    memset(head, -1, sizeof(head));
    while(m--)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dijkstra();
    for(int i=1; i<n; ++i)
        printf("%lld ", dix[i]);
    printf("%lld\n", dix[n]);
    return 0;
}

Bellman-Ford 算法

给定一张有向图，若对于某一条边 (x,y,z) 存在 dist[y]≤dist[x]+z ，则称这条边满足三角不等式。

那么对于一张图而言，若所有的边都满足三角不等式，则 dist 数组就代表起点到其他点的最短路。

我们考虑让所有的边都满足三角不等式，从而求出最短路：
1. 令 dist[s]=0 ，其余的点全部设置为 INF ；
2. 扫描所有的边 (x,y,z) ,若存在 dist[y] ，则令 dist[y]=dist[x]+z；
3. 重复步骤 ，直到没有更新操作发生了（ n-1 次）。

可以处理负权图，但是负环图不存在最短路。

struct Node {
    int x, y, z;
}edge[maxm];
void bellman-ford() {
    for(int i=1; i<=n; ++i) dist[i] = INF;
    dist[s] = 0;
    for(int i=1; i<n; ++i) {
        memcpy(temp, dist, sizeof(dist)); // 把上一轮的结果赋值到 temp 数组中，没有边数限制的时候可以不记录上一轮的
        for(int j=1; j<=m; ++j) {
            int u = edge[j].x;
            int v = edge[j].y;
            int w = edge[j].z;
            dist[v] = min(dist[v], temp[u]+w); //用上一轮的结果更新，可以保证当前的结果经过的边数
        }
    }
}

时间复杂度： O(n*m)。

Q1：如何判断 与哪些点之间不存在最短路？

假设不存在最短路的点是 x 点，直接判断 dist[x] 是否等于 INF 是错的。

需要判断 dist[x] 是否还是和 INF 同一个量级：

我们可以把 INF 设置为题目中最坏情况下的最短路长度的两倍以上，那么当 dist[x]>INF/2 的时候表示 x 与起点之间不存在最短路。

例题3：有边数限制的最短路

把循环到 改成 循环到 就行了。

SPFA 算法

队列优化的 bellman — ford 算法。 SPFA 是 Shortest Path Faster Algorithm 的缩写。
算法流程如下：
1. 建立一个队列，队列里面只含有起点 s ；
2. 取出队头的节点 x ，扫描 x 的所有出边 (x,y,z) ，若 dist[y]>dist[x]+z ，则令 dist[y]=dist[x]+z 。同时若 y 不在队列中，则让 y 进入队列。
3. 重复步骤 2 ，直到队列为空。
一个节点可能进出队列多次，每次进队列都相当于在当前的情况下使得一条边满足三角不等式。最终所有的边都会满足三角不等式，也就说不会再有新的节点入队了。

队列里面的点的 值都是被更新成更小的了，那么这些点的出边就可以继续去更新其他的点。这相较于 算法而言会少扫描很多冗余的点。 算法在随机图上的效率为
。 是一个较小的常数。

但是在网格图上 的时间复杂度为退化到 O(n*m)。

如何优雅的卡SPFA

以【模板】单源最短路径（标准版）的代码为例：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const int maxm = 2e5+10;
const LL INF = (1LL<<31)-1;
int head[maxm], vis[maxn];
LL dix[maxn];
int n, m, s, tot=0;
struct node
{
    int to, nxt, d;
}edge[maxm];
void add(int x, int y, int z)
{
    edge[tot].to = y;
    edge[tot].d = z;
    edge[tot].nxt = head[x];
    head[x] = tot++;
}
void SPFA() {
    queue<int> que;
    for(int i=1; i<=n; ++i) dix[i] = INF;
    memset(vis, 0, sizeof(vis));
    dix[s] = 0; vis[s] = 1;
    que.push(s);
    while(!que.empty()) {
        int x = que.front();
        que.pop();
        vis[x] = 0; // BFS是进出队列一次，标记不还原
        for(int i=head[x]; i!=-1; i=edge[i].nxt) {
            int y = edge[i].to;
            int z = edge[i].d;
            if(dix[y] > dix[x] + z) {
                dix[y] = dix[x] + z;
                if(!vis[y]) {
                    que.push(y);
                    vis[y] = 1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    memset(head, -1, sizeof(head));
    while(m--)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    SPFA();
    for(int i=1; i<n; ++i)
        printf("%lld ", dix[i]);
    printf("%lld\n", dix[n]);
    return 0;
}

如果有负权无负环的情况下， SPFA 如何判断起点与 x 点之间没有最短路？

和 dijkstra 算法一样，判断 dist[x] 是否等于 INF 即可。
只有从头到尾都没有进过队列的点的 dist 值才会是 INF 。所有的点都只被队列中的点更新，就不会出现 dis[x] 被 INF+负权 所更新了。

判断负环

如何判断图中是否存在负环？

只要存在负环，则表明永远不可能使得所有的边都满足三角不等式。

Bellman-Ford 判断负环

若经过了 迭代，所有的边都满足了三角不等式，则图中无负环。

若在第 轮迭代中，仍有能产生更新的边，则表示有负环。

注意： 若要求的是 是否存在一个起点能够到达的负环，则需要判断 第 次迭代中的点，是否与起点相联通。

SPFA判断负环

方法一：

设 cnt[x] 表示起点 s 到 x 的最短路径包含的边数， cnt[s]=0 。当执行 dist[y]=dist[x]+z 时，同样去更新 cnt[y]=cnt[x]+1 。若此时发现 cnt[y]≥n ,则表示图中有负环（且这个负环和起点相连）。

方法二：

如果没有负环，在 SPFA 中每个点最多被更新 n-1 。记录每个点入队的次数，次数达到 n 时，表明有从起点相连的负环。

方法一的效率会更高一点。例如，对于一个 n 个点排列成的负环，方法一只需要绕环一次就能发现负环，方法二需要绕环 n 次。

例题4：【模板】负环

Bellman — Ford 实现

#include <bits/stdc++.h>
using namespace std;
const int maxm = 6e3+10;
const int maxn = 2e3+10;
const int INF = 2e8;
int n, m, Max_m, dist[maxn], temp[maxn];
struct Node {
    int x, y, z;
}edge[maxm];
int bellman_ford() {
    for(int i=1; i<=n; ++i) dist[i] = INF;
    dist[1] = 0;
    int cnt = 0;
    for(int i=1; i<=n; ++i) {
        memcpy(temp, dist, sizeof(dist));
        for(int j=1; j <= Max_m; ++j) {
            int u = edge[j].x;
            int v = edge[j].y;
            int w = edge[j].z;
            if(dist[v] > temp[u]+w) {
                dist[v] = temp[u] + w;
                if(dist[v] < INF/2) // 表示 起点 能走到 v 点，如果 v 点在负环里面，就表示起点能走到负环
                    cnt = i; // cnt记录最后一次更新在cnt轮迭代中
            }
        }
    }
    return cnt;
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        int k=0;
        for(int i=1; i<=m; ++i) {
            k++;
            scanf("%d%d%d", &edge[k].x, &edge[k].y, &edge[k].z);
            if(edge[k].z >= 0) {
                k++;
                edge[k].x = edge[k-1].y;
                edge[k].y = edge[k-1].x;
                edge[k].z = edge[k-1].z;
            }
        }
        Max_m = k;
        int cnt = bellman_ford();
        if(cnt==n) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

SPFA 判定负环，大家自己实现一下。

正常题目中 SPFA 的应用会比 Bellman — Ford 更多，因为除了判定负环外，通常题目还要求不存在负环需要输出最短路。

单源最短路算法总结