05 最短路

userId_undefined
吴老师
7月全勤卷王8月全勤卷王10月全勤卷王倔强青铜时间刺客空间掌握者

2026-06-30 19:12:43

发布于：广东

5阅读
0回复
0点赞

05 最短路：Floyd 与 Dijkstra

一、本阶段目标

学完本阶段，学生要能做到：

1. 区分无权最短路和带权最短路。
2. 掌握 Floyd 求任意两点最短路。
3. 掌握 Dijkstra 求非负边权单源最短路。
4. 能根据数据范围选择算法。
5. 能把“最小费用/最短时间/最小风险”转化为最短路。

二、最短路问题分类

类型 含义 常用算法
无权单源最短路 每条边代价都是 1，从一个起点出发 BFS
带权单源最短路 边权非负，从一个起点出发 Dijkstra
多源最短路 任意两点之间最短路 Floyd
边权有负数 可能需要 Bellman-Ford / SPFA 了解即可

深圳自招主线只需要熟练：

BFS + Floyd + Dijkstra

三、Floyd 算法

Floyd 用来求任意两点之间的最短距离。

适合：

点数较小
需要多次查询两点间最短路

核心思想：

尝试让 k 作为中转点。
如果 i -> k -> j 比 i -> j 更短，就更新。

转移方程：

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

四、Floyd 模板

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

const int N = 505;
const int INF = 1e9;
int d[N][N];

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

    int n, m;
    cin >> n >> m;

    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;
        }
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w); // 无向图
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] < INF && d[k][j] < INF) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }

    return 0;
}

五、Floyd 的复杂度

时间复杂度：O(n^3)
空间复杂度：O(n^2)

适合大致范围：

n <= 300 比较常见
n <= 500 有时可以
n >= 1000 通常不能用 Floyd

六、Dijkstra 算法

Dijkstra 用来求：

从一个起点 s 到所有点的最短路

前提：

所有边权非负

核心思想：

每次选出当前还没确定最短路的点中，dist 最小的点。
用它去更新相邻点。

七、Dijkstra 的直觉解释

假设你从学校出发，到所有地点都想求最短时间。

当前已知有几个候选地点距离学校最近。由于所有道路时间都是非负的：

当前距离最小的那个点，不可能再通过其他更远的点绕回来变得更短。

所以可以把它的最短路“确定”下来。

这也是为什么 Dijkstra 不能处理负边权：

如果后面有负边，可能绕一圈后距离反而变短。

八、堆优化 Dijkstra 模板

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

using ll = long long;
const int N = 100005;
const ll INF = 4e18;

vector<pair<int, int>> g[N];
ll dista[N];
bool vis[N];

void dijkstra(int s, int n) {
    for (int i = 1; i <= n; i++) dista[i] = INF;

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    dista[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (vis[u]) continue;
        vis[u] = true;

        for (auto [v, w] : g[u]) {
            if (dista[v] > dista[u] + w) {
                dista[v] = dista[u] + w;
                pq.push({dista[v], v});
            }
        }
    }
}

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

    int n, m, s;
    cin >> n >> m >> s;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    dijkstra(s, n);

    for (int i = 1; i <= n; i++) {
        if (dista[i] == INF) cout << "INF ";
        else cout << dista[i] << ' ';
    }

    return 0;
}

九、Dijkstra 的复杂度

使用优先队列：

O((n + m) log n)

适合：

n, m 很大
边权非负
从一个起点出发

十、Floyd 和 Dijkstra 怎么选

情况 选择
边权全是 1 BFS
点数小，问任意两点 Floyd
点数大，从一个起点出发 Dijkstra
多次单源查询 多次 Dijkstra 或 Floyd，视 n、m 而定
有负边 不用 Dijkstra，另学 Bellman-Ford/SPFA

十一、常见建模关键词

题面关键词 图论模型
最短时间 最短路
最小费用 最短路
最小消耗 最短路
最大成功率 可转化为最短路或优先队列贪心
最少换乘 BFS 或最短路
路径风险最小 最短路，或最小化最大边权

十二、最小化最大边权模型

有些题不是求路径边权和最小，而是要求路径上最大边权尽量小。

例如：

从 A 到 B，要让经过道路中最危险的一条路的危险值尽量小。

转移可以写成：

if (dist[v] > max(dist[u], w)) {
    dist[v] = max(dist[u], w);
}

这仍然可以用 Dijkstra 思想，因为状态值也满足“越小越优”。

洛谷 P1396 营救就是类似模型。

十三、Floyd 常见错误

错误 后果 修正
没有初始化 d[i][i]=0 自己到自己距离错误 初始化对角线为 0
INF 太小 加法溢出或错误更新 用足够大的 INF
忘记处理重边 答案偏大 min(d[u][v], w)
k 循环顺序错 Floyd 语义被破坏 必须 k 在最外层

十四、Dijkstra 常见错误

错误 后果 修正
用于负权图 答案错误 确认边权非负
int 溢出 路径和错误 dist 用 long long
忘记 vis 或旧状态判断 重复处理多 可用 vis 或 if (d != dist[u]) continue
无向图只加一条边 路径缺失 双向加边
多组数据不清空 数据污染 清空 g、vis、dist

十五、练习题

题号 题名 训练点 建议
P3371 单源最短路径（弱化版） Dijkstra 基础 必做
P4779 单源最短路径（标准版） 堆优化 Dijkstra 必做
P1119 灾后重建 Floyd + 时间限制 必做
P1359 租用游艇 Floyd 入门 必做
P1144 最短路计数 最短路 + 计数 提高
P1396 营救 最小化最大边权 提高
P1576 最小花费 最短路建模 提高
P1629 邮递员送信 正反图 Dijkstra 提高

链接：

https://www.luogu.com.cn/problem/P3371
https://www.luogu.com.cn/problem/P4779
https://www.luogu.com.cn/problem/P1119
https://www.luogu.com.cn/problem/P1359
https://www.luogu.com.cn/problem/P1144
https://www.luogu.com.cn/problem/P1396
https://www.luogu.com.cn/problem/P1576
https://www.luogu.com.cn/problem/P1629

十六、本阶段作业

  1. 写出 Floyd 的三重循环，并解释 k 为什么在最外层。
  2. 写出 Dijkstra 模板，并说明优先队列里存什么。
  3. 完成 P3371、P4779。
  4. 完成 P1119，理解“随着时间开放节点”的变式。
  5. 选做 P1396，体会最短路不一定是“求和最小”。

十七、本阶段小结

选择最短路算法时，先问：

边权是不是全为 1？
是否只有一个起点？
是否需要任意两点？
点数大不大？
有没有负权？

对应关系：

无权：BFS
小图多源：Floyd
大图非负单源：Dijkstra
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论