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

最近被BOSS抽查 运筹学 基本功课,

面对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)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2017-09-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员算法基础——动态规划

1928
来自专栏新智元

【干货】谷歌 TensorFlow Fold 以静制动,称霸动态计算图

【新智元导读】谷歌日前推出深度学习动态图计算工具 TensorFlow Fold,可以根据不同结构的输入数据建立动态的计算图,简化训练阶段输入数据的预处理过程,...

3383
来自专栏机器人网

滚珠丝杠你知多少,滚柱丝杠你又知多少?

滚珠丝杠的是将螺杆轴与螺母滚道内装进钢珠后进行无限的滚动和循环的一种机械形式,从而产生将旋转运动转化为精确直线定位运动。为减少钢珠在滚道内循环时产生的摩擦力矩,...

3479
来自专栏数据和云

神马?SQL竟然可以解脑筋急转弯的题目?

我在很多公开演讲中都明目张胆的羡慕过一类人,他们把SQL当做艺术,把旁人眼中的枯燥演绎成经典,云和恩墨专家团队中的杨廷琨、罗海雄就都是这样的SQL专家。 今天,...

3294
来自专栏大数据智能实战

基于stanford nlp(JAVA)实现关系抽取

关系抽取是自然语言处理和理解的重要任务之一,就是从自由文本中发现实体对(人物、地点、机构、事件)及实体之间的关系。 关系抽取一般采用三元组,(实体,关系,实体)...

5655
来自专栏数说工作室

哈希函数的套路 | 文本分析:大规模文本处理(1)

这个系列打算以文本相似度为切入点,逐步介绍一些文本分析的干货。 第一篇中,介绍了文本相似度是干什么的; 第二篇,介绍了如何量化两个文本,如何计算余弦相似度,穿...

4548
来自专栏工科狗和生物喵

【机器视觉与图像处理】基于MATLAB的角度计算

我一开始还苦思冥想,不知道怎么才能提取出来这个因素,所以很是烦恼不知道该如何是好,但是昨天看了下群里面的说法,我瞬间就理通了。只要转变下思维,把图像看成一个二维...

1041
来自专栏机器之心

入门 | 玩转词向量:用fastText预训练向量做个智能小程序

6129
来自专栏码神联盟

智能对话 | 使用 Java实现 智能对话机器人 -- 附源码

目前人工智能与深度学习顺应了互联网时代潮流,人机对话已经成为目前人工智能领域中非常热门的处理技术。其中基于深度学习的人机对话交换系统(智能机器人)是人工智能最有...

1.6K2
来自专栏python学习之旅

算法学习笔记(二):贪心算法

1823

扫码关注云+社区