0. 亿点废话
我实在是太闲了，连创作计划这种东西都写
广子
温馨提示，本帖适合已经学习过图的人食用，不然看不懂别怪我
初学者找资料乱讲中，勿喷，不是AI。啥也不懂
由于作者不太擅长MarkDownMarkDownMarkDown以及LaTeXLaTeXLaTeX，所以大家凑活看吧，如有建议还请多多指教。
特别声明：本帖有参考一些资料中的数据，文本部分为完全原创，严禁抄袭
好了不说了让我们切入正题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 概念
最短路算法是解决 “从图中一个顶点到另一个顶点的路径中，边的权值之和最小的路径” 这一问题的一种快捷方式。在 C++ 开发中，最短路算法广泛应用于地图导航、网络路由、物流规划等场景。
1. 图的基本定义
在最短路问题中，“图” 是由顶点（VertexVertexVertex） 和边（EdgeEdgeEdge） 组成的数据结构，记为 GGG = (VVV, EEE)，其中：
* 顶点（VVV）：代表问题中的 “节点”，如地图中的城市、网络中的设备；
* 边（EEE）：代表顶点之间的 “连接关系”，如城市间的公路、设备间的通信线路；
* 边的权值（WeightWeightWeight）：边的 “代价”，如公路的长度（可正可负）。
2. 最短路问题的分类
根据问题场景，最短路问题主要分为两类：
* 单源最短路：从图中一个固定顶点（源点） 到其他所有顶点的最短路径，如 “从北京到全国所有城市的最短路线”；
* 多源最短路：从图中所有顶点到其他所有顶点的最短路径，如 “全国任意两个城市之间的最短路线”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 作用
注：此段内部分资料来源于网络
最短路算法是解决最短路问题的一种高效工具，其作用体现在以下场景：
1. 地图导航与路径规划
这是最短路算法最直观的应用。例如，导航软件计算 “从起点到终点的最短距离 / 时间”，本质是对 “城市道路图”（顶点 = 路口 / 地点，边 = 道路，权值 = 距离 / 时间）求解单源最短路，常用 Dijkstra\mathtt{Dijkstra}Dijkstra 算法（无负权）或 AAA * 算法（Dijkstra\mathtt{Dijkstra}Dijkstra 的优化）。
2. 网络通信与路由优化
在计算机网络中，路由器需要选择 “从源 IP 到目标 IP 的最优链路”，避免网络拥堵。此时，“网络拓扑图”（顶点 = 路由器，边 = 通信链路，权值 = 延迟 / 丢包率）的最短路计算，常用 Bellman−Ford\mathtt{Bellman-Ford}Bellman−Ford算法（支持负权，应对链路故障导致的权值变化）。
3. 物流与资源调度
物流企业规划 “从仓库到多个配送点的最优路线”，或工厂调度 “原材料运输的最低成本路径”，本质是多源最短路问题，可通过Floyd−Warshall\mathtt{Floyd-Warshall }Floyd−Warshall 算法快速计算任意两点间的最优路径，降低运营成本。
4. 其他场景
如游戏开发中的 “NPC 寻路”（地图格子作为顶点，移动代价作为权值）、电路设计中的 “信号传输最短路径” 等，均依赖最短路算法的核心逻辑。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 用法
在 C++ 中实现最短路算法，首先需要选择图的合适存储方式，再根据问题场景选择算法。以下是关键步骤与用法说明：
1. 图的存储方式
常用的图存储结构有两种，需根据算法需求选择：
* 邻接矩阵（AdjacencyMatrix\mathtt{Adjacency Matrix}AdjacencyMatrix）：用二维数组 [N][N] 存储，g[u][v] 表示顶点u到v的边权（无连接则设为无穷大）。适合顶点数少（N≤1000N≤1000N≤1000）的场景，Floyd−Warshall\mathtt{Floyd-Warshall}Floyd−Warshall 算法常用此结构。
* 邻接表（AdjacencyList\mathtt{Adjacency List}AdjacencyList）：用 vector 数组 vector< pair<int, int> > adj[N] 存储，adj[u] 中的每个元素 (v`, w) 表示顶点u到v的边权为w。适合边数少（稀疏图）的场景，Dijkstra\mathtt{Dijkstra}Dijkstra、Bellman−Ford\mathtt{Bellman-Ford }Bellman−Ford算法常用此结构。
2. 各算法的核心用法
1. DIJKSTRA\MATHTT{DIJKSTRA}DIJKSTRA 算法（单源、无负权）
C++ 实现关键步骤：
1. 用邻接表存储图；
2. 用dist[N]数组记录源点到各顶点的最短距离（初始化为无穷大，源点距离设为 0）；
3. 用优先队列维护 “待处理的顶点”，每次取出距离最小的顶点，更新邻接顶点的距离；
4. 重复步骤 3，直到优先队列为空。
2. BELLMAN−FORD\MATHTT{BELLMAN-FORD}BELLMAN−FORD 算法（单源、支持负权）
C++ 实现关键步骤：
1. 用邻接表或边集数组存储图；
2. 初始化dist[N]数组（源点为 0，其余为无穷大）；
3. 循环N-1次，对每条边(uuu,vvv, www)执行松弛操作：if (dist[v] > dist[u] + w) dist[v] = dist[u] + w；
4. 检查是否存在负权回路：对每条边再次执行松弛操作，若能更新则存在负权回路。
3. FLOYD−WARSHALL\MATHTT{FLOYD-WARSHALL}FLOYD−WARSHALL 算法（多源）
C++ 实现关键步骤：
1. 用邻接矩阵存储图（dp[N][N]，初始化为边权，dp[i][i] = 0）；
2. 三重循环：for (k=1; k<=N; k++) for (i=1; i<=N; i++) for (j=1; j<=N; j++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])；
最终dp[i][j]即为iii到jjj的最短距离。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 总结
在 C++ 开发中，最短路算法的应用需遵循 “场景匹配” 原则：无负权、单源、大数据规模用 Dijkstra\mathtt{Dijkstra}Dijkstra 算法；有负权、需检测回路用 Bellman−Ford\mathtt{Bellman-Ford}Bellman−Ford 算法；多源、小规模数据用 Floyd−Warshall\mathtt{Floyd-Warshall}Floyd−Warshall 算法。同时，需根据图的稠密 / 稀疏 特性选择存储结构，确保代码效率与正确性，最终解决最短路问题。
