运筹学教学 | 十分钟快速掌握最短路算法（附C++代码及算例）

面对BOSS的突然发问，

机智的小编果断选择了——

拿 · 出 · 课 · 本

然后BOSS 微微一笑 ：

“来，实现下解决这个问题的代码。”

意识到上完运筹学的自己根本是条 只会解应用题 的 咸·鱼，而运筹学实际上是门算法课后...

小编 放弃治疗 痛定思痛 ，决心开始手脑结合、理论+实践、以解决问题为目的，开始自己在运筹学上的新一轮征程！

本着一贯的无私奉献精神，小编整理出了这些日子学习运筹学的一系列心得笔记，帮助大家快速突破理论到实践的次元壁！

运筹学·教学笔记 第一弹 —— 最短路问题篇 先行奉上！熟悉的攻略三连（问题、方法、实现）、熟悉的实践演示、熟悉的代码算例...手把手带你走上 运筹学·大佬 的征程！

＊

内容提要：

＊什么是最短路问题

＊单源最短路问题

＊全局最短路问题

1.什么是最短路问题

最短路问题（shortest-path problem）是图论中的经典问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

基本内容是：假设网络中的每条边都有一个 权重（常用长度、成本、时间等表示），最短路问题的目标是找出 给定两点（通常是源节点和汇节点）之间总权重之和最小的路径。

最短路示例

如上图所示，以1为起点，7为终点，则在此图中，最短路径即为 1—4—2—7。

• 常见的最短路问题 ？

根据问题约束和目标的差异，用来解决问题的算法也会有区别。最短路问题常见的类型有：

-单源最短路问题-

包括

（1）给定起点的最短路径问题，即给定起点，求最短路的问题；

（2）给定终点的最短路径问题，在无向图中等同于给定起点问题，在有向图中等同于路径方向相反的给定起点问题。

-全局最短路问题-

即求解任意两点间的最短路的问题。

• 最短路问题的应用领域？

最短路问题作为图论中的经典问题，其算法的选择与实现是通道路线设计的基础,因此一直是运筹学，计算机科学与地理信息科学等领域的研究热点。

-城市网络-

运用最短路原理可以解决交通运输管理系统中的问题，具有非常重要的现实意义。

根据实时交通状况，赋予城市路网中每段线路以时间权值，利用最短路原理，计算出车辆运行时间最短的路线并汇总，通过手机及时向广大群众发布信息，指导广大群众选择行驶路线，进一步提高现有道路通行能力，提高道路服务水平。

-舰船通道-

利用图论的经典理论和人群流量理论研究舰船人员通道路线的优化设计及最优线路选择。

对船舶通道进行路网抽象,建立网络图,然后以行程时间（根据人群流动的相关理论,选取不同拥挤情况下的人员移动速度,从而确定各条路段(包括楼梯)的行程时间）作为通道网络的路权，得出路阻矩阵以选择一对起点/终点的最短时间路线为目标,建立最短路径问题的数学模型,利用经典的算法确定最短路径。

上述方法可应用于舰艇多层甲板的通道网络设计及其相关问题中。

此外，很多网络相关问题均可纳入最短路径问题的应用范畴之中，如，火灾救护，物流选址，网络空间建设 等等。

2.单源最短路问题

对于Dijkstra算法解决不了的负权边（图中边的权重存在负数的情况）单源最短路问题，就需要介绍解决带负权边图十分有用的另一种算法——SPFA算法。

相关算法的代码将和下一部分全局最短路问题的算法代码一起放出。

3.全局最短路问题

单源最短路、全局最短路问题的相关算法代码和算例如下：

代码及算例示例

代码（c++版本）

算例演示

算例示例

输入文件格式为：

SAMPLE INPUT:

n m

7 11

x y z

2 4 2

1 4 3

7 2 2

3 4 3

5 7 5

7 3 3

6 1 1

6 3 4

2 4 3

5 6 3

7 2 1

PS. n 为图中点数，m为边的数量；

z 为连接 x 结点和 y 结点的边的权值。

输出结果为：

SAMPLE OUTPUT

0 5 5 3 4 1 6

5 0 4 2 6 6 1

5 4 0 3 7 4 3

3 2 3 0 7 4 3

4 6 7 7 0 3 5

1 6 4 4 3 0 7

6 1 3 3 5 7 0

PS. 输出结果为最短路矩阵，矩阵第 i 行、第 j 列的值即表示第 i 个结点到第 j 个结点的最短路长度。

算例演示

如上图红线所示，以1为起点，7为终点，则在此图中，最短路径即为 1—4—2—7。

上述代码仅供分享交流学习用，如有需要复制下面链接自取 ↓ ↓ ↓

http://paste.ubuntu.com/25527580/

或直接戳文章底部的 阅读原文，跳转代码页面！

运筹学·教学笔记 第一弹 —— 最短路问题篇 画上句点！如果大家对 最短路问题 及 文中所叙内容 还有疑问或想要交流心得建议，欢迎移步留言区！

呦呦呦！最后一起为运筹学啊，来段freestyle啊！学习学习，呦，一起学习！哦吼，运筹学，呦呦，嘿！

—end—

编辑：谢良桢（1922193128@qq.com）

贺兴（hexing15@gmail.com）

代码：贺兴（hexing15@gmail.com）

指导老师：秦时明岳（professor.qin@qq.com）