C++ 与算法 · 学习分享平台

知识脉络

按学习顺序组织的六个模块，每块都对应可运行的代码实现。

语言基础与 STL

vector / deque / priority_queue / unordered_map 的适用场景与复杂度；迭代器与引用语义、RAII 与资源管理；复杂度估算的基本方法。

vector：连续内存，尾插均摊 O(1)；中间插入/删除 O(n)；扩容会使迭代器、引用、指针全部失效。
priority_queue：默认大顶堆；小顶堆要写 greater<int>；复杂度 O(log n)。
unordered_map：平均 O(1)、最坏 O(n)（哈希退化）；键为自定义类型需提供 hash 与 ==。
deque：双端队列，头尾插入均 O(1)，SPFA 里用作队列比 vector 省事。
RAII：资源获取即初始化；现代写法用 unique_ptr / shared_ptr 管理，避免裸 new/delete。

建图与数据存储

邻接表与邻接矩阵的取舍（稀疏图用邻接表）；从 CSV、OSM Overpass、在线地铁数据解析建图；节点编号与坐标投影。

稀疏图（m ≪ n²）用邻接表：空间 O(n+m)，遍历某点所有出边 O(度)；稠密图才考虑邻接矩阵 O(n²)。
无向边存两次（u→v 与 v→u），有向边存一次；重边一般取权值最小那条。
带权图常用 vector<vector<pair<int,int>>>（to, w）或 struct Edge {to, w, next}。
节点编号统一从 0 或 1 开始，不要混用；坐标单独存数组，画地图时再做投影。
解析 CSV / JSON 时先读入点表与边表再建图；缺失坐标要能兜底（否则渲染异常）。

单源最短路

Dijkstra 贪心成立的前提是边权非负；朴素版 O(n²) 适合稠密图，堆优化版 O((n+m)log n) 适合稀疏图；距离与前驱数组复原路径。

前提：所有边权非负。有负权必须换 Bellman-Ford / SPFA，否则贪心失效。
朴素 O(n²)：每轮线性扫描 dis 取最小，实现最简单，稠密图反而更快。
堆优化 O((n+m)log n)：优先队列 + 懒删除（出堆时若 d != dis[u] 则跳过）——工程首选。
复原路径：pre[v] 记录"最短路上的前一个点"，从终点回溯到起点再反转。
正确性直觉：非负权时，当前最小的 dis 不可能再被别人更新，故"出堆即最终"。

负权与负环

Bellman-Ford 做 n-1 轮松弛、第 n 轮仍有更新则存在负环；SPFA 用队列减少无效松弛；注意无向图的负权边等价于负环。

Bellman-Ford：对所有边做 n-1 轮松弛；若第 n 轮仍有边能松弛 ⇒ 存在负环，最短路无意义。
SPFA：只把"距离被更新过的点"入队，稀疏图上通常很快；最坏仍 O(nm)，竞赛中可能被卡。
判负环也可用"某点入队次数 > n"或"松弛轮数 > n-1"。
易错：无向图里出现负权边，等于可以来回走无限减小距离 ⇒ 一定构成负环。
BF 天然按"轮"推进，很适合做动画演示（本项目 3D 分层沙盘就按轮着色）。

全源最短路

Floyd-Warshall 是以中转点 k 为阶段的矩阵 DP，O(n³)；用 next / parent 矩阵复原任意两点路径；点数大时需慎用。

循环顺序必须是 k → i → j（k 在最外层），这是"以中转点为阶段"的 DP 顺序，写错就错。
转移：dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])。
复杂度 O(n³)、空间 O(n²)：n ≤ 400 尚可，n 上千时改用"以每个点为源跑 Dijkstra"。
路径复原另存 next[i][j]（i 到 j 的第一个后继），更新时同步改。
初始化：dis[i][i] = 0，未直接连的边为 INF；INF 要留出加法余量防止溢出（如 4e18 会溢出 ll）。

DP 进阶与建模

状压 DP 求多点巡回路线（TSP）；时变交通网把边权写成出发时刻的分段函数，按时间推进做最短路查询。

状压 DP：dp[s][i] = 已访问集合 s、当前停在 i 的最小代价；s 用二进制位掩码表示。
TSP 复杂度 O(2^k · n²)，k ≤ 20 左右可行；更大规模只能贪心/近似（最近邻）。
时变网络：边权是出发时刻的函数，状态要加一维时间，不能直接用静态最短路。
记忆化搜索（dfs + 缓存）写起来比递推直观，状态少时优先用。
本项目的多点巡回：k ≤ 12 用状压 DP 精确解，否则退化为最近邻贪心并标注差距。

↑ 返回本页目录

关键代码速览

可直接粘到 C++ 在线运行环境里跑的精简片段（省略头文件的部分请自行补全）。

① 邻接表建图

const int INF = 0x3f3f3f3f;             // 比 1e18 安全：相加不溢出 int
struct Edge { int to, w; };
vector<vector<Edge>> g(n + 1);          // 编号从 1 开始

void addEdge(int u, int v, int w) {     // 有向边
    g[u].push_back({v, w});
}
void addUndir(int u, int v, int w) {    // 无向边：存两次
    g[u].push_back({v, w});
    g[v].push_back({u, w});
}

② 堆优化 Dijkstra

vector<int> dis(n + 1, INF), pre(n + 1, -1);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
dis[s] = 0; pq.push({0, s});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d != dis[u]) continue;          // 懒删除：过期条目直接跳过
    for (auto e : g[u]) {
        int v = e.to, w = e.w;
        if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w;
            pre[v] = u;                 // 记录前驱，用于复原路径
            pq.push({dis[v], v});
        }
    }
}

③ Floyd-Warshall 核心（注意循环顺序）

for (int k = 1; k <= n; k++)            // k 必须在最外层：以中转点为阶段
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dis[i][k] + dis[k][j] < dis[i][j])
                dis[i][j] = dis[i][k] + dis[k][j];

④ 状压 DP（TSP）

int FULL = 1 << n;
vector<vector<int>> dp(FULL, vector<int>(n, INF));
dp[1][0] = 0;                            // 从 0 号点出发
for (int s = 1; s < FULL; s++)
    for (int i = 0; i < n; i++) {
        if (dp[s][i] == INF || !(s >> i & 1)) continue;
        for (int j = 0; j < n; j++)
            if (!(s >> j & 1))
                dp[s | (1 << j)][j] = min(dp[s | (1 << j)][j], dp[s][i] + w[i][j]);
    }
int ans = dp[FULL - 1][0];               // 回到起点的最短巡回

易错点清单

INF 溢出：用 1e18 做无穷大时，dis[u] + w 可能越过 long long 上限；本项目改用 4e17（远大于真实路径、又离 LLONG_MAX 很远）。
Floyd 循环顺序写反：k 放内层就完全错了，结果看似"差不多"但不正确。
无向图的负权边：等价于负环，Dijkstra 会给出错误答案且不报错，很难查。
忘记懒删除：优先队列里旧条目不出堆也能得到正确结果，但会多做很多无用松弛。
重边与自环：建图时未去重会让复杂度虚高；自环一般不影响最短路但需注意判负环逻辑。
编号从 0 还是 1 混用：数组开 n+1 但循环到 n-1，是最常见的越界来源。
复原路径时 pre 未初始化：不连通的点 pre 应保持 -1，回溯时才能判断"不可达"。

↑ 返回本页目录

编程练习

先自己写，再点开解答对照；解答代码可直接粘到 C++ 在线运行环境里跑。

编程题 1 · 堆优化 Dijkstra（入门）

题目：输入 n 个点 m 条无向带权边（权值非负）与起点 s，输出 s 到每个点的最短距离，不可达输出 −1。
输入示例：4 4 1 表示 4 点 4 边、起点 1；随后每行 u v w。
提示：优先队列存 (距离, 点)，小顶堆；出堆时若 d != dis[u] 直接跳过。

查看解答（可粘到在线运行环境）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct E { int to, w; };
int main() {
    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<E>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});          // 无向边：存两次
    }
    const int INF = 1e9;
    vector<int> dis(n + 1, INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dis[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dis[u]) continue;       // 懒删除
        for (auto e : g[u])
            if (dis[e.to] > dis[u] + e.w) {
                dis[e.to] = dis[u] + e.w;
                pq.push({dis[e.to], e.to});
            }
    }
    for (int i = 1; i <= n; i++)
        cout << (dis[i] == INF ? -1 : dis[i]) << (i == n ? "" : " ");
    return 0;
}

编程题 2 · 判断负环（Bellman-Ford）

题目：给定 n 点 m 条有向边（权值可为负），判断图中是否存在从起点可达的负环，有则输出 YES，否则输出最短路长度。
提示：做 n−1 轮松弛后，再对所有边检查一次；若仍能松弛 ⇒ 存在负环。
易错：无向图里的负权边等价于负环；INF 要留足加法余量，别溢出。

查看解答（可粘到在线运行环境）

#include <iostream>
#include <vector>
using namespace std;
struct E { int u, v, w; };
int main() {
    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<E> es;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        es.push_back({u, v, w});
    }
    const long long INF = 4e17;          // 远离 LLONG_MAX，防止 dis+w 溢出
    vector<long long> dis(n + 1, INF);
    dis[s] = 0;
    for (int i = 1; i <= n - 1; i++) {
        bool any = false;
        for (auto e : es)
            if (dis[e.u] != INF && dis[e.v] > dis[e.u] + e.w) {
                dis[e.v] = dis[e.u] + e.w; any = true;
            }
        if (!any) break;                 // 提前收敛
    }
    for (auto e : es)                    // 第 n 轮：还能松弛就是负环
        if (dis[e.u] != INF && dis[e.v] > dis[e.u] + e.w) {
            cout << "YES" << endl;
            return 0;
        }
    cout << (dis[n] == INF ? -1 : dis[n]) << endl;
    return 0;
}

编程题 3 · Floyd 求全源最短路（小图）

题目：n ≤ 100，给定邻接矩阵（0 表示自己到自己、−1 表示无边），求任意两点间最短距离。
提示：三重循环，k（中转点）必须在最外层；初始化 dis[i][i] = 0。
扩展：想复原路径，可另存 next[i][j] 表示 i→j 的第一个后继点。

查看解答（可粘到在线运行环境）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    if (!(cin >> n)) return 0;
    const int INF = 1e9;
    vector<vector<int>> dis(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int w; cin >> w;
            if (i == j) dis[i][j] = 0;
            else if (w >= 0) dis[i][j] = w;
        }
    for (int k = 0; k < n; k++)              // k 必须在最外层
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dis[i][k] + dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << (dis[i][j] == INF ? -1 : dis[i][j]) << (j + 1 == n ? "" : " ");
        cout << endl;
    }
    return 0;
}

↑ 返回本页目录

算法对照

同一份图数据下的选型依据，也是本项目六种实现并存的原因。

算法	适用场景	时间复杂度	负权	要点
Dijkstra（朴素）	单源、非负权、稠密图	O(n²)	不支持	每轮线性扫描取最小，实现最简
Dijkstra（堆优化）	单源、非负权、稀疏图	O((n+m) log n)	不支持	优先队列 + 懒删除，工程首选
Bellman-Ford	单源、含负权、需判负环	O(nm)	支持，可判负环	按轮松弛，天然适合做动画演示
SPFA	单源、含负权	平均 O(km)，最坏 O(nm)	支持，可判负环	队列优化，稀疏图上常最快
Floyd-Warshall	全源最短路	O(n³)	支持（无负环）	矩阵 DP，点数 > 400 时开销显著
状压 DP（TSP）	多点巡回路线	O(2^k · n²)	—	k 为必经点数量，指数级只适合小规模

实测参考（随机图 3000 点、m = 5n）：朴素 Dijkstra 13.3 ms、堆优化 0.66 ms、SPFA 0.30 ms、Bellman-Ford 0.57 ms。

↑ 返回本页目录

实践项目：SP-Shortest

以真实城市地铁网络与 OSM 路网为数据源的完整实现，已进入云服务器运行。

单源最短路四件套

朴素 Dijkstra、堆优化 Dijkstra、Bellman-Ford（含负环判定）、SPFA，支持逐节点输出距离与前驱路径。

Floyd-Warshall 全源

矩阵式动态规划求任意两点最短距离与路径，配"矩阵舞台"动画逐步展示 k 轮松弛过程。

多点巡回 TSP

状压 DP 求访问多个目标点的最小耗时巡回路线，适合地铁"打卡路线"场景。

时变与分层图最短路

分层图最短路：状态扩展为 (站点, 层)。换乘模式以线路为层、跨线加换乘惩罚并给出换乘点；时变模式以时段为层（早高峰 7-9 / 平峰 / 夜间），查询指定出发时刻的最优路线。

真实数据接入

在线获取高德地铁图线路数据、OSM Overpass 真实路网，也支持本地 CSV / 文本图导入。

Qt 动画可视化

Bellman-Ford 按轮扩散动画、Floyd 全图拼装进度、任意两点路径高亮与节点标签。

↑ 返回本页目录

可视化成果

以下截图由 Qt 可视化程序渲染后随项目一并上传。

Bellman-Ford 按轮扩散动画（北京 411 站） — **Bellman-Ford 按轮扩散** · 北京地铁 411 站，青色表示本轮被松弛的节点

Bellman-Ford 按轮扩散动画（南昌 113 站） — **Bellman-Ford 按轮扩散** · 南昌地铁 113 站

Floyd 全图拼装 k=112 — **Floyd 全图拼装** · k 轮推进至 100%，矩阵舞台逐步收敛

Floyd 矩阵舞台（北京 k=286） — **Floyd 矩阵舞台** · 北京网络 k=286 阶段

↑ 返回本页目录

文档、源码与运行

两份讲解文档提供网页版在线阅读与 Word 下载；源码打包为 tar.gz；Linux 命令行版已编译。

在线阅读讲解文档在线阅读代码实例版下载 Word（讲解）下载 Word（代码实例版）下载源码包

项目	值
服务器目录	/opt/sp_shortest
可执行文件	/opt/sp_shortest/shortest（Linux x86-64，命令行菜单式）
构建脚本	Windows build.bat（MinGW） / Linux build_linux.sh（g++）
Qt 图形界面	qtview 为 Windows 桌面组件，服务器无图形环境，云端提供命令行版

# 在服务器上运行（菜单式命令行）
cd /opt/sp_shortest && ./shortest

# 从源码重新编译 Linux 版
cd /opt/sp_shortest && bash build_linux.sh

↑ 返回本页目录

工程经验与踩坑

实际开发中记录下来的问题，按主题分类。

算法与对拍

无向图带负权边等价于负环：生成含负权的随机图时必须转为有向，否则任何最短路算法都会判定负环。
对拍校验的边界：起点等于终点时，路径复原返回单点，不能用"路径权值和 == dis"校验，应改为判断 dis == 0。
一致性验证：正权场景下五算法互比、负权场景 SPFA 与 Bellman-Ford 互比、负环必须被检出，三类用例缺一不可。

跨平台与构建

平台隔离：windows.h / wininet / Sleep / GetTickCount 一律用 #ifdef _WIN32 包裹，非 Windows 分支用 curl + popen 下载、sleepMs / tickMs 替代。
Windows 链接：build.bat 需显式 -lwininet，否则 HTTP 抓取部分链接失败。
命令行陷阱：findstr 无匹配时退出码为 1，会截断 && 命令链，容易误判编译失败。

Qt 可视化

运行依赖：直接双击 exe 报 0xC0000135 时，是缺 Qt 动态库，需把 C:\Qt\6.8.0\mingw_64\bin 加入 PATH。
代码位置：UI 主逻辑集中在头文件（main_window.h / map_view.h），同名 .cpp 多为占位，搜索时不要只看 .cpp。
动画节拍：动画总时长需按算法轮数自适应（如 max(3.5s, 0.22s × 轮数)），否则轮数多时每轮一闪而过无法观察。
3D 透明度：着色器未开启混合，QColor 的 alpha 无效，"半透明"必须用 RGB 预混色模拟。

代码组织

自检钩子：启动自检代码（环境变量触发的无头回归）从构造函数抽出到独立头文件，在类定义之后 include，行为不变但主文件体积减半。
模块拆分：随机图生成、对拍验证、性能基准、教学演示各自独立成模块，主菜单统一入口调用。

↑ 返回本页目录

笔记与后续

待补充：手写学习笔记（Markdown）、课后习题与实现记录；可放在本页末尾新增区块，或单独成页后在此处加链接。

已实现：分层图最短路（换乘代价 / 时变时段）——扩展图 + 分层 Dijkstra，CLI 菜单 5 可跑，Qt 侧按 L 键在图上按层着色播放并标出换乘 / 跨时段点。 后续候选主题：A* 启发式搜索、双向 Dijkstra、Johnson 全源算法、最小生成树与最短路的关系、网络流入门。

↑ 返回本页目录