零、公共基础：数据类型与图结构
所有算法共用同一套基础设施，先把它读透，后面每个算法才好对照。
（一）距离类型与无穷大
边权是「分钟」，可能累加很多段，所以用 64 位整数 long long；无穷大取 1e18 而不是 INT_MAX，是为避免两段 dis[u]+w 相加时整数溢出。
// common/common.h
typedef long long ll;
const ll INF = 1e18;（二）Graph：邻接表 + 邻接矩阵双存
这是本项目一个设计取舍：邻接表 g_ 用于 Dijkstra/Bellman-Ford/SPFA 的「枚举每个点的出边」（邻接表枚举最快）；邻接矩阵 a_ 用于 Floyd 的「随机访问两点之间有没有边、权多少」（矩阵 O(1) 访问）。两条数据一起维护，各取所长。
// cheng/graph.h（节选）
struct Edge { int to; ll w; };
class Graph {
bool dir_;
int n_, m_, dropped_;
std::vector<bool> alive_; // 标记哪些点还活着（支持删点）
std::vector<std::vector<Edge> > g_; // 邻接表：g_[u] = u 的所有出边
std::vector<std::vector<ll> > a_; // 邻接矩阵：a_[u][v] = 权值 / INF
};（三）前驱还原路径 getPath
所有单源算法都只记录 pre[v]（v 是从谁松弛来的）。要输出具体走法，用 getPath 从终点沿 pre 倒推回起点。它做了三层越界/成环防御，避免坏数据触发未定义行为。
// common/common.h
inline std::vector<int> getPath(int s, int t, const std::vector<int>& pre) {
std::vector<int> res;
const int n = (int)pre.size();
if (s < 0 || s >= n || t < 0 || t >= n) return res; // 起终点越界
if (s == t) return std::vector<int>(1, s);
for (int v = t; v != s; v = pre[v]) {
if (v < 0 || v >= n) return std::vector<int>(); // 前驱越界
if ((int)res.size() > n) return std::vector<int>(); // 前驱成环，防御
res.push_back(v);
}
res.push_back(s);
std::reverse(res.begin(), res.end());
return res;
}一、Dijkstra 朴素版（O(n²)）
核心思想：贪心。每次从「还没确定最短路的点」里挑一个当前距离最小的，把它永久确定下来（因为它不可能再被松弛得更小——所有边权非负），再用它去松弛邻居。
// cheng/dijkstra.cpp —— dijkstraNaive
void dijkstraNaive(const Graph& g, int s, std::vector<ll>& dis, std::vector<int>& pre) {
int n = g.n();
dis.assign(n, INF);
pre.assign(n, -1);
dis[s] = 0;
std::vector<int> vis(n, 0); // vis=1 表示该点最短路已经确定
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) { // 每次 O(n) 扫一遍找距离最小的点
if (!g.ok(j) || vis[j]) continue;
if (u == -1 || dis[j] < dis[u]) u = j;
}
if (u == -1 || dis[u] == INF) break; // 剩下的都到不了，提前结束
vis[u] = 1; // 永久确定 u
const std::vector<Edge>& t = g.adj(u);
for (int j = 0; j < (int)t.size(); j++) { // 用 u 松弛所有邻居
int v = t[j].to;
ll w = t[j].w;
if (dis[u] + w < dis[v]) { // 松弛
dis[v] = dis[u] + w;
pre[v] = u;
}
}
}
}逐行解读
vis[u]=1是「确定」标记：只有未被确定的点才有资格当下一轮的最小点。- 「找最小点」那层
for j是 O(n)，整体做 n 次，所以复杂度 O(n²)。稠密图（边数接近 n²）时这版反而比堆优化快（堆有 log 常数）。 if (u==-1 || dis[u]==INF) break：剩下的点都不可达，没必要再扫，直接收工。- 负权边会出错：因为确定后不再反悔；一旦有负权，可能本该被「从后面绕回来」更新得更小，但点已被锁死。
二、Dijkstra 堆优化版（O((n+m)log n)）
把「找最小点」换成优先队列（小根堆），每次取堆顶即可，省掉 O(n) 扫描。
// cheng/dijkstra.cpp —— dijkstraHeap
void dijkstraHeap(const Graph& g, int s, std::vector<ll>& dis, std::vector<int>& pre) {
int n = g.n();
dis.assign(n, INF); pre.assign(n, -1); dis[s] = 0;
typedef std::pair<ll, int> P; // (dist, node)
std::priority_queue<P, std::vector<P>, std::greater<P> > q; // 小根堆
q.push(std::make_pair(0, s));
std::vector<int> vis(n, 0);
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue; // 过期的进堆项，直接丢掉
vis[u] = 1; // 此时一定是「当前最小且未确定」的点
const std::vector<Edge>& t = g.adj(u);
for (int j = 0; j < (int)t.size(); j++) {
int v = t[j].to; ll w = t[j].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w; pre[v] = u;
q.push(std::make_pair(dis[v], v)); // 入堆（可能重复）
}
}
}
}关键难点：为什么 if (vis[u]) continue; 不能省
易错点：一个点
v 可能被多次入堆（第一次 dis=5 入堆，后来又被松弛成 dis=3 再入堆）。堆里会有两份 v。当 3 那份先被弹出并 vis[v]=1 后，5 那份再被弹出来时，vis[v] 已经是 1，必须跳过，否则会用旧的大距离再去松弛邻居，得到错误结果。这就是「惰性删除」——不真删堆里的旧项，弹出时再判一次。这正是你项目 411 节点实测里真正在跑的版本。复杂度
每个点最多入堆一次（确定后不再入），每条边松弛时可能入堆一次，共 O(n+m) 次入堆，每次堆操作 O(log n)，故 O((n+m)log n)。稀疏图（地铁网边数远小于 n²）优势巨大。
三、Dijkstra 记录型（供动画重放）
逻辑与堆版完全一致，唯一新增：把「被确定的点」按时间顺序收进 order，动画模块就能按这个顺序一帧帧点亮节点。
// cheng/dijkstra.cpp —— dijkstraRecorded
void dijkstraRecorded(const Graph& g, int s, std::vector<int>& order,
std::vector<ll>& dis, std::vector<int>& pre) {
int n = g.n();
dis.assign(n, INF); pre.assign(n, -1); order.clear();
if (s < 0 || s >= n || !g.ok(s)) return;
typedef std::pair<ll, int> ND;
std::priority_queue<ND, std::vector<ND>, std::greater<ND> > pq;
std::vector<char> done(n, 0);
dis[s] = 0; pq.push(ND(0, s));
while (!pq.empty()) {
ND top = pq.top(); pq.pop();
int u = top.second;
if (done[u] || top.first > dis[u]) continue; // 双重守卫
done[u] = 1;
order.push_back(u); // ← 记录「确定顺序」，喂给动画
const std::vector<Edge>& es = g.adj(u);
for (size_t k = 0; k < es.size(); ++k) {
int v = es[k].to;
if (v < 0 || v >= n || !g.ok(v)) continue;
ll nd = dis[u] + es[k].w;
if (nd < dis[v]) { dis[v] = nd; pre[v] = u; pq.push(ND(nd, v)); }
}
}
}双重守卫
done[u]：等价于堆版的vis[u]，挡掉已确定的点。top.first > dis[u]：挡掉「堆里的旧距离项」——即使点没被确定过，但堆顶这份距离比当前已知dis[u]还大，说明是过期项。比堆版只查vis更显式，写动画重放时更不易出错。
三个 Dijkstra 函数同源：朴素 / 堆 / 记录型只是「取最小点的方式」和「是否记录顺序」不同。改一处逻辑记得同步另两处。
四、Bellman-Ford（支持负权）
Dijkstra 负权会出错，Bellman-Ford 可以处理负权、并检测负环。做法是「逐轮松弛所有边」，最多 n-1 轮就收敛。
// cheng/bellman_ford.cpp —— bellmanFord
bool bellmanFord(const Graph& g, int s, std::vector<ll>& dis, std::vector<int>& pre) {
int n = g.n();
dis.assign(n, INF); pre.assign(n, -1);
if (!g.ok(s)) return false;
dis[s] = 0;
for (int i = 1; i <= n - 1; i++) { // 最多 n-1 轮
bool flag = false; // 本轮是否发生过松弛
for (int u = 0; u < n; u++) {
if (!g.ok(u) || dis[u] == INF) continue;
const std::vector<Edge>& t = g.adj(u);
for (int j = 0; j < (int)t.size(); j++) {
int v = t[j].to; ll w = t[j].w;
if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; pre[v] = u; flag = true; }
}
}
if (!flag) break; // 没有任何边被松弛 ⇒ 已收敛，提前停
}
// 再来一轮：若还能松弛，说明存在从 s 可达的负环
for (int u = 0; u < n; u++) {
if (!g.ok(u) || dis[u] == INF) continue;
const std::vector<Edge>& t = g.adj(u);
for (int j = 0; j < (int)t.size(); j++) {
int v = t[j].to;
if (dis[u] + t[j].w < dis[v]) return false; // 负环 ⇒ 返回 false
}
}
return true;
}讲解
- 为什么 n-1 轮：任何最短路最多经过 n-1 条边；每轮至少能把「最短路边数 +1」的点的正确距离固定下来，所以 n-1 轮必收敛。
flag提前收敛：实际图往往远早于 n-1 轮就稳定，flag=false即停，省时间。- 负环检测：若前 n-1 轮后还能松弛，说明有一条能不停绕圈变小的路径——返回
false，调用方据此提示「无解」。
记录型 bellmanFordRecorded 额外按轮次收集 order 和每轮松弛边数 roundInfo，正好能可视化「一圈一圈向外铺开」的节奏，与 Dijkstra 的「逐点确定」形成对照。
五、SPFA（队列优化）
Bellman-Ford 每轮都扫全部边，很浪费。SPFA 只把「被松弛过的点」入队，下一轮只处理队里的点——很多图上快得多（期望约 O(m)）。
// cheng/spfa.cpp —— spfa
bool spfa(const Graph& g, int s, std::vector<ll>& dis, std::vector<int>& pre) {
int n = g.n();
dis.assign(n, INF); pre.assign(n, -1);
if (!g.ok(s)) return false;
dis[s] = 0;
std::vector<int> inq(n, 0), cnt(n, 0); // inq=是否在队；cnt=入队次数
std::queue<int> q;
q.push(s); inq[s] = 1; cnt[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop(); inq[u] = 0; // 出队
const std::vector<Edge>& t = g.adj(u);
for (int j = 0; j < (int)t.size(); j++) {
int v = t[j].to; ll w = t[j].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w; pre[v] = u;
if (!inq[v]) {
q.push(v); inq[v] = 1; cnt[v]++;
if (cnt[v] >= n) return false; // 入队 n 次 ⇒ 负环
}
}
}
}
return true;
}讲解
inq[]避免同一点重复入队；inq[u]=0在出队时清除，松弛时若不在队才再入。- 负环判定：若一个点入队 ≥ n 次，说明它在一条不停变小的负环上，直接返回
false。这是 SPFA 相对 Bellman-Ford 更紧凑的负环检测写法。 - 最坏复杂度 O(nm)：存在特意构造的图让 SPFA 退化为 Bellman-Ford。所以本项目把 SPFA 作为「可对比的底座」而非默认主力——默认主力是堆 Dijkstra。
六、Floyd 全源最短路
上面四个都是「单源」。Floyd 一次性算出任意两点之间的最短路，核心就一句：允许以 k 为中转时，i→j 是否更短。
// cheng/floyd.cpp —— floyd（节选核心三层循环）
for (int k = 0; k < n; k++) { // ① 中转点 k 必须放在最外层！
if (!g.ok(k)) continue;
for (int i = 0; i < n; i++) {
if (!g.ok(i) || dis[i][k] == INF) continue;
for (int j = 0; j < n; j++) {
if (!g.ok(j) || dis[k][j] == INF) continue;
if (dis[i][k] + dis[k][j] < dis[i][j]) { // 松弛
dis[i][j] = dis[i][k] + dis[k][j];
next[i][j] = next[i][k]; // 记录路径中转
}
}
}
}最易写错、且静默算错的地方：循环顺序必须是
k → i → j。k 必须在最外层，含义是「先让所有路径都允许经过 0..k-1 中转，再开放 k」。如果把 k 放内层，更新 dis[i][k] 时用的还是没经过前面中转的旧值，结果会悄悄算错而不报错——这是答辩时最常被追问的点，务必讲清。路径还原
next[i][j] 存「i 到 j 的第一步走向」。还原时不断跳 next[u][j] 直到抵达 j：
// cheng/floyd.cpp —— floydPath
std::vector<int> floydPath(const std::vector<std::vector<int> >& next, int i, int j, int n) {
std::vector<int> res;
if (i < 0 || i >= n || j < 0 || j >= n) return res;
if (next[i][j] == -1) return res; // 不可达
if (i == j) { res.push_back(i); return res; }
int u = i;
while (u != j) {
res.push_back(u);
u = next[u][j];
if (u == -1) { res.clear(); return res; } // 防御
}
res.push_back(j);
return res;
}复杂度 O(n³)，与边数无关。当要查的起终点对数 k 接近 n 时，一次 Floyd 比 k 次 Dijkstra 更划算（见下一章巡回的底座选型）。
七、多目标巡回：状态压缩 DP
「从起点出发，以最优顺序访问多个目标点，总耗时最短」——这是 TSP 的变体（不要求回起点）。项目把它拆成两步，两步各自可选算法。
（一）两步拆解
- 第①步 距离矩阵：求「起点 + 各目标」两两最短路，得到 k×k 矩阵 D（k = 目标数+1）。底座可选：k 次 Dijkstra / k 次 SPFA / 一次 Floyd。
- 第②步 顺序求解：在矩阵 D 上决定访问顺序。精确解用状态压缩 DP（Held-Karp），目标多到 2^m 爆炸时退化为最近邻贪心。
（二）距离矩阵层（底座选型）
// cheng/multitarget.cpp（节选）—— 按 baseAlgo 选底座
if (baseAlgo == TOUR_FLOYD) {
std::vector<std::vector<ll> > dd; std::vector<std::vector<int> > nx;
if (!floyd(g, dd, nx)) return false; // 一次 Floyd 拿全源
for (int i = 0; i < k; ++i)
for (int j = 0; j < k; ++j)
D[i][j] = dd[list[i]][list[j]]; // 取表内点的值
} else {
for (int i = 0; i < k; ++i) {
std::vector<ll> dis; std::vector<int> pre;
if (baseAlgo == TOUR_SPFA) { if (!spfa(g, list[i], dis, pre)) return false; }
else dijkstraHeap(g, list[i], dis, pre); // 默认：k 次堆 Dijkstra
for (int j = 0; j < k; ++j) D[i][j] = dis[list[j]];
}
}实测（411 节点、5 个目标）：k×Dijkstra 0.79ms，Floyd 643ms——慢约 800 倍却结果相同。因为 k=6 远小于 n，Floyd 把整个 411×411 全算了一遍是浪费。结论：k 接近 n 才该用 Floyd，否则多次 Dijkstra 更优。
（三）顺序求解：状态压缩 DP
定义 dp[mask][i] = 已访问集合为 mask、当前停在目标 i 的最小总耗时。转移：从 i 走到未访问的 j，状态变为 mask | (1<<j)。
// cheng/multitarget.cpp（节选）—— Held-Karp 状态压缩 DP
int full = 1 << m; // 2^m 个状态
std::vector<std::vector<ll> > dp(full, std::vector<ll>(m, INF));
for (int j = 0; j < m; ++j) { // 初始化：从起点 0 直接到目标 j
ll d = D[0][j + 1];
if (d < INF / 2) dp[1 << j][j] = d;
}
for (int mask = 1; mask < full; ++mask) {
for (int i = 0; i < m; ++i) {
if (!(mask & (1 << i)) || dp[mask][i] >= INF / 2) continue;
for (int j = 0; j < m; ++j) {
if (mask & (1 << j)) continue; // j 已访问，跳过
ll nd = dp[mask][i] + D[i + 1][j + 1];
int nm = mask | (1 << j);
if (nd < dp[nm][j]) { dp[nm][j] = nd; par[nm][j] = i; }
}
}
}
// 取最优终点，并沿 par 回溯出访问顺序
int last = -1; ll best = INF;
for (int i = 0; i < m; ++i)
if (dp[full - 1][i] < best) { best = dp[full - 1][i]; last = i; }
total = best;边界与退化
- 状态规模 2^m·m：m=20 时约 2000 万格，明显卡顿。所以
m > 12时 AUTO 模式自动退化为最近邻贪心；显式要求精确解但m > 20直接返回 false（标「不可用」），而不是硬跑卡死。 - 回溯时用
par[mask][cur]一步步往起点推，再 reverse 即得顺序。
八、碰头点选址（minimax / minisum）
这是本项目最有「生活感」的原创设计：几个人从不同出发地出发，找一个点让大家碰头。同一张图、同一套最短路，换目标函数，答案就不同。
（一）求解内核 solveMeet
// qtview/main.cpp（节选）—— solveMeet
// 每个出发点各跑一次单源最短路，得到 D[k][v] = 第 k 人到点 v 的耗时
for (size_t k = 0; k < meetSrc_.size(); ++k) {
std::vector<ll> dis; std::vector<int> pre;
dijkstraHeap(g, meetSrc_[k], dis, pre); // 复用堆 Dijkstra
D.push_back(dis); P.push_back(pre);
}
// 逐个候选点 v 打分
ll bestMax = INF, bestSum = INF;
for (int v = 0; v < n; ++v) {
if (!g.ok(v)) continue;
ll mx = 0, sum = 0; bool reach = true;
for (size_t k = 0; k < D.size(); ++k) {
ll d = D[k][v];
if (d >= INF / 2) { reach = false; break; } // 有人到不了 ⇒ 淘汰 v
if (d > mx) mx = d; // minimax：最远那人的耗时
sum += d; // minisum：所有人总耗时
}
if (!reach) continue;
if (mx < bestMax) { bestMax = mx; fairOut = v; } // fairOut：最公平
if (sum < bestSum) { bestSum = sum; cheapOut = v; } // cheapOut：最省
}两种目标函数
| 准则 | 目标函数 | 含义 | 适用 |
|---|---|---|---|
| minimax（最公平） | minᵥ maxₖ disₖ[v] | 让「最吃亏的那个人」尽量不吃亏 | 大家地位平等 |
| minisum（最省） | minᵥ Σₖ disₖ[v] | 所有人总路程最短 | 总能耗/总成本低 |
（二）对照组：忽略拥堵会怎样
computeMeet 在主结果（含拥堵 gWork_）之外，还用一份「去掉拥堵系数」的图再算一次 meetNoJam_。诚实结论：光有真实拥堵系数时，碰头点常常不变——因为各人来路上的拥堵程度接近，相对关系没变；只有叠加高峰模拟（J 键）才会真正改变选址。这个「反例」本身很有说服力。
// qtview/main.cpp（节选）—— computeMeet 的对照
Graph gNoJam = net_.graph(); // 基础图（无拥堵系数）
// 仅保留封路：把被封的边权设为 kBlocked
for (size_t i = 0; i < closed_.size(); ++i) {
int u = closed_[i].first, v = closed_[i].second;
if (gNoJam.hasEdge(u, v)) gNoJam.setW(u, v, kBlocked);
}
int f2 = -1, c2 = -1;
solveMeet(gNoJam, f2, c2, NULL, NULL); // 不含拥堵再算一次
meetNoJam_ = f2; // 与含拥堵的解对比九、拥堵系数建模（数据驱动）
项目自带的城市 CSV 大多只有 3 列（起点,终点,分钟），没有拥堵系数——那时「按拥堵算」等于没算。本工具用真实经纬度 + 真实拓扑推算系数，而非随机数。
（一）系数公式
# tools/gen_congestion.py —— factor_of（节选）
def factor_of(u, v, ctx, coord):
deg, center, dist_c, max_d, seg_len, max_len = ctx
# 向心性：区间中点离质心越近越挤（指数衰减，集中到核心区）
du, dv = dist_c.get(u, 0.0), dist_c.get(v, 0.0)
rel = min(1.0, (du + dv) / 2.0 / max_d)
centrality = (1.0 - rel) ** CENTER_EXP # CENTER_EXP = 2.0
# 换乘站：任一端度数≥3 ⇒ 客流叠加
hub = 1.0 if (deg.get(u, 0) >= HUB_DEG or deg.get(v, 0) >= HUB_DEG) else 0.0
# 长区间（郊区快线）相对宽松
long_ratio = min(1.0, seg_len.get((u, v), 0.0) / max_len)
f = 1.0 + W_CENTER * centrality + W_HUB * hub - W_LONG * long_ratio
return max(F_MIN, min(F_MAX, round(f, 2))) # 截断到 [1.0, 1.9]为什么衰减指数必须 > 1
取
CENTER_EXP = 1.0（线性）时，离质心不算远的中环区间也拿到高系数，全城中位约 1.66、几乎「一起堵」，区分度太差，最短路/碰头点照样不变。取 2.0（平方）后压到 1.00~1.76：质心 ×1.8、中环 ×1.3、远郊 ×1.05，空间差异才拉开。北京最堵的西单—灵境胡同 ×1.76。（haversine 用真实经纬度算大圆距离，纬度取绝对值处理数据里存成负值的情况。）（二）整体对比速查
| 算法 | 类型 | 复杂度 | 负权 | 本项目角色 |
|---|---|---|---|---|
| Dijkstra 堆 | 单源 | O((n+m)log n) | 否 | 默认主力（计算/对比/巡回底座） |
| Dijkstra 朴素 | 单源 | O(n²) | 否 | 教学演示 |
| Bellman-Ford | 单源 | O(nm) | 是 | 负权/负环检测 |
| SPFA | 单源 | 期望O(m)/最坏O(nm) | 是 | 对比底座/负环 |
| Floyd | 全源 | O(n³) | 否 | k≈n 时巡回底座 |
| 巡回 DP | 多目标 | O(m·2^m) | 取决于底座 | m≤12 精确，否则贪心 |
| 碰头 solveMeet | 选址 | O(P·n·log n) | 否 | minimax/minisum |