最短路

zifuneko · 2024-10-20 18:43:31 · 算法·理论

Upd(Learn) on Oct.4th, 2025.

最短路

下文将会用到的一些记号的含义。

• $(u,v)$ 这一条边的边权。

性质

• 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。

• 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。

• 对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过 𝑛，边数不会超过 n-1。

\text{Dijkstra}

是一种求解 非负权图 上单源最短路径的算法。其过程主要是每次选取离 S 最近的点，然后更新。

松弛操作

对于边 (u,v)，松弛操作对应下面的式子：

含义显然，当尝试用 S \to u \to v（其中 S \to u 的路径取最短路）这条路径去更新 v 点最短路的长度，如果这条路径更优，就进行更新。

在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 +1，而最短路的边数最多为 n-1，因此整个算法最多执行 n-1 轮松弛操作。故时间复杂度为 O(n)。

但还有一种情况，如果从 S 点出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 n-1 轮，因此如果第 n 轮循环时仍然存在能松弛的边，说明从 S 点出发，能够抵达一个负环。

::::error[错误]{open} 注意到证明过程中的关键不等式 D(y) \leq D(u) 是在图上所有边边权非负的情况下得出的。当图上存在负权边时，这一不等式不再成立，Dijkstra 算法的正确性将无法得到保证，算法可能会给出错误的结果。 ::::

过程

将结点分成两个集合：已确定最短路长度的点集（记为 S 集合）的和未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合。

初始化 dis(s)=0，其他点的 dis 均为 +\infty。

然后重复这些操作：

1. 从 T 集合中，选取一个最短路长度最小的结点，移到 S 集合中。
2. 对那些刚刚被加入 S 集合的结点的所有出边执行松弛操作。

直到 T 集合为空，算法结束。

\text{Dijkstra} 朴素实现

【板】P3371 【模板】单源最短路径（弱化版）

朴素的实现方法为每次 2 操作执行完毕后，直接在 T 集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为 O(m)，1 操作总时间复杂度为 O(n^2)，全过程的时间复杂度为 O(n^2 + m)。

适合稠密图，即 m>n^2.

复杂度为 O(n^2+m)

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX = 1e5+5;
const int INF = (1<<31)-1;

struct Edge{int v, w;};
vector<Edge> e[MAX];
int n, m, s, vis[MAX], dis[MAX];

void dijkstra()
{
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[s] = 0;
    for(int i=1; i<=n; i++)
    {
        int u=0, mind=INF;
        for(int j=1; j<=n; j++)
            if(!vis[j] && dis[j] < mind)
                u = j, mind = dis[j];
        vis[u] = 1;
        for(auto t : e[u])
            dis[t.v] = min(dis[t.v], dis[u] + t.w);
    }
}

signed main()
{
    cin >> n >> m >> s;
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
    }
    dijkstra();
    for(int i=1; i<=n; i++) cout << dis[i] << ' ';

    return 0;
}

\text{Dijkstra} 优先队列维护

可以使用优先队列维护，可以通过每次松弛时重新插入该结点，且弹出时检查该结点是否已被松弛过，若是则跳过，复杂度 O(m\log n)，优点是实现较简单。

【板】P4779 【模板】单源最短路径（标准版）

适合稀疏图，即 n<m<n^2。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX = 2e5+5;
const int INF = (1<<31)-1;

struct Edge{
    int v, w;
    bool operator>(const Edge& a) const {return w > a.w;}
};
priority_queue<Edge, vector<Edge>, greater<Edge>> q;
vector<Edge> e[MAX];
int n, m, s, vis[MAX], dis[MAX];

void dijkstra()
{
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[s] = 0;
    q.push({s, 0});

    while(!q.empty())
    {
        int u = q.top().v;
        q.pop();

        if(vis[u]) continue;
        vis[u] = 1;
        for(auto t : e[u])
            if (dis[t.v] > dis[u] + t.w) 
                dis[t.v] = dis[u] + t.w, 
                q.push({t.v, dis[t.v]});
    }
}

signed main()
{
    cin >> n >> m >> s;

    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
    }
    dijkstra();
    for(int i=1; i<=n; i++) cout << dis[i] << ' ';

    return 0;
}

迪杰斯特拉最短路计数

P1144 最短路计数

• 如果 dis[v]>dis[u]+w：那么就说明找到了优的路径，将 v 的路径计数用 u 的路径计数覆盖，即ans[y] = ans[x]。

• 如果 dis[v]=dis[u]+w：则说明两条路径长度相同，那么 v 就加上 u 的计数，即 ans[y] += ans[x]。

  
  #include<bits/stdc++.h>
  using namespace std;

const int MAX = 2e6+5; const int MOD = 100003; struct Edge { int v, w; bool operator>(const Edge &a) const {return w > a.w;}; }; vector<Edge> d[MAX]; priority_queue<Edge, vector<Edge>, greater<Edge>> q; int n, m, s=1, dis[MAX], vis[MAX], ans[MAX]; void dijkstra() {
memset(dis, 0x3f, sizeof(dis)); dis[s] = 0; ans[s] = 1; q.push({s, 0});

while(!q.empty())
{
    int u = q.top().v; q.pop();
    if(vis[u]) continue; vis[u] = 1;

    for(auto t : d[u])
    {
        if(dis[t.v] > dis[u] + t.w) // 找到更短路径将ans替换
            dis[t.v] = dis[u] + t.w,
            ans[t.v] = ans[u],
            q.push({t.v, dis[t.v]});
        else if(dis[t.v] == dis[u] + t.w) 
            ans[t.v] += ans[u],
            ans[t.v] %= MOD;
    }
}

}

int main() { cin.tie(nullptr)->ios::sync_with_stdio(false);

cin >> n >> m;
for(int i=1; i<=m; i++)
{
    int x, y;
    cin >> x >> y;
    d[x].push_back({y, 1});
    d[y].push_back({x, 1});
}

dijkstra();
for(int i=1; i<=n; i++) cout << ans[i] << endl;
return 0;

}

## $\text{Bellman Ford}$

$\text{Bellman–Ford}$ 算法是一种基于松弛操作的最短路算法，可以求出有**负权的图**的最短路，并可以对最短路不存在的情况进行判断。

如果你不知道松弛操作，请上翻至 $\text{Dijkstra} \to 松弛操作$。

$\text{Bellman–Ford}$ 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 $+1$，而最短路的边数最多为 $n-1$，因此，当每次循环是 $O(m)$ 的时，整个算法最多执行 $n-1$ 轮松弛操作。故时间复杂度为 $O(nm)$。

但还有一种情况，如果从 $S$ 点出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 $n-1$ 轮，因此如果第 $n$ 轮循环时仍然存在能松弛的边，说明从 $S$ 点出发，能够抵达一个负环。

::::warning[负环判断的误区]{open}
需要注意的是，以 $S$ 点为源点跑 $\text{Bellman–Ford}$ 算法时，如果没有给出存在负环的结果，只能说明从 $S$ 点出发不能抵达一个负环，而不能说明图上不存在负环。

因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个**超级源点**，向图上每个节点连一条权值为 $0$ 的边，然后以超级源点为起点执行 $\text{Bellman–Ford}$ 算法。
::::

```cpp
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX = 1e5+5;
const int INF = (1<<31)-1;

struct Edge{int u, v, w;};
vector<Edge> e;
int n, m, s, dis[MAX];

bool bellman_ford()
{
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[s] = 0;

    bool flag = 0; // 判断一轮循环过程中是否发生松弛操作
    for(int i=1; i<=n; i++)
    {
        flag = false;
        // 对每一条边进行松弛操作
        for(auto t : e)
        {
            // 最短路长度为 INF 的点引出的边不可能发生松弛操作
            if(dis[t.u] == INF) continue;
            if(dis[t.v] > dis[t.u] + t.w)
                dis[t.v] = dis[t.u] + t.w,
                flag = true; 
        }
        // 没有可以松弛的边时就停止算法
        if(flag == false) break;
    }
    // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
    return flag;
}
signed main()
{
    freopen("P3371_2.in", "r", stdin);
    cin >> n >> m >> s;
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e.push_back((Edge){u, v, w});
    }
    bellman_ford();
    for(int i=1; i<=n; i++) cout << dis[i] << ' ';

    return 0;
}

(UnUpd) 还可以求负环

参考题目：P3385 【模板】负环

R146214711 记录详情

#include<bits/stdc++.h>
using namespace std;

struct Edge{
    int to, w;
};

long long n,m,dis[100005];
vector<Edge> mp[100005];
const long long INF = ((long long)1<<31)-1;

int bellman_ford(int s)
{
    for(int i=1;i<=n;i++) dis[i] = INF;
    dis[s] = 0;
    int cnt;
    for(int i=1;i<=n;i++)
    {
        cnt = 0;
        for(int j=1;j<=n;j++)
        {
            for(int k=0;k<mp[j].size();k++)
            {
                Edge t = mp[j][k];
                if(dis[t.to] > dis[j]+t.w && dis[j]<INF)
                {
                    dis[t.to] = dis[j]+t.w;
                    cnt ++;
                }
            }
        }
        if(cnt == 0) return 0;
    }
    if(cnt > 0) return 1;
}

void out(int i)
{
    if(i) cout << "YES" << endl;
    else cout << "NO" << endl;
    return;
}

int main()
{
    int T;
    cin >> T;

    for(int i=1;i<=T;i++)
    {
        for(int j=0;j<=n;j++) mp[j].resize(0);
        cin >> n >> m;
        for(int j=1;j<=m;j++)
        {
            int u,v,w;
            cin >> u >> v >> w;
            if(w >= 0)
            {
                mp[u].push_back((Edge){v,w});
                mp[v].push_back((Edge){u,w});
            }
            else mp[u].push_back((Edge){v,w});
        }
        out(bellman_ford(1));
    }
    return 0;
}

队列优化：\bold{\text{SPFA}}

即 Shortest Path Faster Algorithm。

很多时候我们并不需要那么多无用的松弛操作。

很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。

那么我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。

SPFA 也可以用于判断 s 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 n 条边时，说明 s 点可以抵达一个负环。

参考题目：

P3371 【模板】单源最短路径（弱化版）

P3385 【模板】负环

同上，如果需要求负环，即可将 out 函数在输出地方套入 SPFA 函数。

#include<bits/stdc++.h>
using namespace std;

struct Edge{
    int to, w;
};

long long n,m,s,dis[100005];
int cnt[100005];
bool vis[100005];
vector<Edge> mp[100005];
const long long INF = ((long long)1<<31)-1;

int spfa()
{
    queue<int> q;
    for(int i=1;i<=n;i++) dis[i] = INF, cnt[i] = 0;
    dis[s] = 0;
    q.push(s);
    vis[s] = true;
    cnt[s] ++;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for(int i=0;i<mp[t].size();i++)
        {
            Edge temp = mp[t][i];
            if(dis[t] < INF && dis[temp.to] > dis[t]+temp.w)
            {
                dis[temp.to] = dis[t]+temp.w;
                if(vis[temp.to] == false)
                {
                    q.push(temp.to);
                    vis[temp.to] = true;
                    if(cnt[temp.to] > n) return 1;
                }
            }
        }
    }
    return 0;
}

void out(int i)
{
    if(i) cout << "YES" << endl;
    else cout << "NO" << endl;
    return;
}

int main()
{
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        mp[u].push_back((Edge){v,w});
    }
    spfa();
    for(int i=1;i<=n;i++) cout << dis[i] << ' ';
}

\text{Floyd}

是用来求任意两个结点之间的最短路的。

复杂度为 O(n^3)，容易实现。

适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）

实现

定义一个数组 f[k][x][y]，表示只允许经过结点 1 到 k，结点 x 到结点 y 的最短路长度。

显然，f[n][x][y] 就是结点 x 到结点 y 的最短路长度。

其中 f[k-1][x][y]，为不经过 k 点的最短路径，而 f[k-1][x][k]+f[k-1][k][y]，为经过了 k 点的最短路。

特殊的 f[k][x][y] 情况，当 x = y 的时候为零，因为到本身的距离为零；当 x 与 y 没有直接相连的边的时候，为 +\infty。

for (k = 1; k <= n; k++)
  for (x = 1; x <= n; x++)
    for (y = 1; y <= n; y++)
      f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);

因为第一维对结果无影响，我们可以发现数组的第一维是可以省略的，于是可以直接改成 f[x][y] = min(f[x][y], f[x][k]+f[k][y])。

for (k = 1; k <= n; k++) 
  for (x = 1; x <= n; x++) 
    for (y = 1; y <= n; y++) 
      f[x][y] = min(f[x][y], f[x][k] + f[k][y]);

综上时间复杂度是 O(N^3)，空间复杂度是 O(N^2)。

B3647 【模板】Floyd

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, f[105][105];

void floyd()
{
    for(int k=1; k<=n; k++)
        for(int x=1; x<=n; x++)
            for(int y=1; y<=n; y++)
                f[x][y] = min(f[x][y], f[x][k]+f[k][y]);
}

int main()
{
    cin >> n >> m;
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) f[i][i] = 0;

    for (int i = 0; i < m; i++) 
    {
        int u, v, w;
        cin >> u >> v >> w;
        f[u][v] = min(f[u][v], w);
        f[v][u] = min(f[v][u], w);
    }
    floyd();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << f[i][j] << " ";
        cout << endl;
    }
    return 0;
}

参考题目：P2910 [USACO08OPEN] Clear And Present Danger S

#include<bits/stdc++.h>
using namespace std;
int n, m, ans=0, mp[105][105], a[10005];

int floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(mp[i][k] + mp[k][j] < mp[i][j]) mp[i][j] = mp[i][k] + mp[k][j];
}

int main()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++) cin >> a[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin >> mp[i][j];

    floyd();
    for(int i=1;i<m;i++) ans += mp[a[i]][a[i+1]];
    cout << ans << endl;

    return 0;
}

好题 P1119 灾后重建

注意点：

• 在 floyd 过程中不可以中断，即下方代码中的update，否则动态规划正确性会出现问题；
• 注意 f[i][k] + f[k][j] 可能会出现溢出的问题；
• 在做题时仔细思考 f[k][x][y] 的含义。

#include<bits/stdc++.h>
using namespace std;

// f[k][x][y]，表示只允许经过结点 1 到 k，结点 x 到结点 y 的最短路长度。

int n, m, t[205], f[205][205];
const int INF = 0x3f3f3f3f;

void update(int p)
{
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            f[i][j] = min(f[i][j], f[i][p] + f[p][j]);
}

signed main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> t[i];

    memset(f, 0x3f, sizeof(f));
    for(int i=0; i<n; i++) f[i][i] = 0;

    for(int i=1; i<=m; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        f[x][y] = w;
        f[y][x] = w;
    }
    int Q, cur=0; cin >> Q;
    while(Q--)
    {
        int x, y, q;
        cin >> x >> y >> q;
        while(t[cur] <= q && cur < n)
            update(cur), cur++;
        if(t[x] > q || t[y] > q || f[x][y] == INF) cout << -1 << endl;
        else cout << f[x][y] << endl;
    }

    return 0;
}