44 | 最短路径：地图软件是如何计算出最优出行路径的？
王争
该思维导图由 AI 生成，仅供参考
基础篇的时候，我们学习了图的两种搜索算法，深度优先搜索和广度优先搜索。这两种算法主要是针对无权图的搜索算法。针对有权图，也就是图中的每条边都有一个权重，我们该如何计算两点之间的最短路径（经过的边的权重和最小）呢？今天，我就从地图软件的路线规划问题讲起，带你看看常用的最短路径算法（Shortest Path Algorithm）。
像 Google 地图、百度地图、高德地图这样的地图软件，我想你应该经常使用吧？如果想从家开车到公司，你只需要输入起始、结束地址，地图就会给你规划一条最优出行路线。这里的最优，有很多种定义，比如最短路线、最少用时路线、最少红绿灯路线等等。作为一名软件开发工程师，你是否思考过，地图软件的最优路线是如何计算出来的吗？底层依赖了什么算法呢？
算法解析
我们刚提到的最优问题包含三个：最短路线、最少用时和最少红绿灯。我们先解决最简单的，最短路线。
解决软件开发中的实际问题，最重要的一点就是建模，也就是将复杂的场景抽象成具体的数据结构。针对这个问题，我们该如何抽象成数据结构呢？
我们之前也提到过，图这种数据结构的表达能力很强，显然，把地图抽象成图最合适不过了。我们把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就在两个顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了地图软件如何利用最短路径算法进行路线规划，以及Dijkstra算法的原理和应用。文章首先介绍了深度优先搜索和广度优先搜索算法，然后引出了针对有权图的最短路径算法。地图软件如Google地图、百度地图、高德地图等利用这些算法，根据用户输入的起始和结束地址，计算出最优的出行路线，包括最短路线、最少用时路线、最少红绿灯路线等。读者可以通过本文了解地图软件背后的最短路径算法原理，以及如何应用到实际的路线规划中。此外，文章还引申了Dijkstra算法的应用，提出了一个翻译系统的问题，并探讨了如何借助Dijkstra算法的核心思想高效地解决该问题。最后，文章提出了一些课后思考问题，包括如何获得通过某条路的时间以及如何规划公交出行路线等。整体而言，本文深入浅出地介绍了最短路径算法及其在地图软件中的应用，同时展示了算法思想在其他领域的潜在应用，对读者具有一定的启发意义。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(99)
- 最新
- 精选
Liam有2个疑问： 1 Dijkstra就是贪心算法吧？ 2 它的解可能不是最优解作者回复: Dijkstra实际上可以看做动态规划：）
2019-01-08827
yongxiang王老师，我输入代码运行后，实际出队列的顺序跟图中的不一样，实际（15，0）出队列 在（13，3）出队列前面。我看了代码，应该是修改（25，1）为 （13，3）的时候，小顶堆不会自动更新顺序。需要对22行进行如下修改，更新已经在队列中，又改了dist的Vertex的优先级： if (inQueue[nextVertex.id] == false){ queue.add(nextVertex); inQueue[nextVertex.id] = true; } else { // 更新已经在队列中，又改了dist的Vertex的优先级 queue.remove(nextVertex); queue.add(nextVertex); }作者回复: 嗯嗯 我更新下代码
2019-01-129
小刚za0b0c0扩展后可以得到之后会得到三个组合,a1b0c0,a0b1c0,a0,b0,c1，请问一下这三个组合是怎么推导出来的作者回复: a0b0c0 -》 a1b0c0： a0->a1 其他的不变； a0b0c0 -》 a0b1c0： b0->b1 其他的不变； a0b0c0 -》 a0b0c1： c0->c1 其他的不变. 比a0b0c0第二小的数据肯定出现在这三个候选中。
2019-05-212
hughieyu更新vertex后是否要更新一下对象在优先级队列中的位置，否则会预期更晚弹出优先级队列，会影响查找的速度，除此之外还没有可能出现其他的问题作者回复: 会自动更新位置的 相当于堆中更新一个节点的值
2019-01-072- Geek_dddebb亲测更新vertex后对象在队列中的位置不变
作者回复: 代码已经改正，你再看下？；）
2019-01-0721 
魏全运vertex compareTo有问题吧，怎么没有相等的分支呀？作者回复: 有也可以 没有也可以的
2019-01-071
张三在图的搜索算法那一节只是提到一句广度优先搜索算法的结果是最短路径，并没有说原因😂作者回复: 好像有讲到
2019-09-034
i 星星老师，如果这个要是取权重最大该怎么设计呢？作者回复: 😅，这个需求就不是最短路径问题了
2019-08-312
mike如果构造的图中有环，是否存在inqueue标记已入队的顶点需要update dist时，其实该顶点已经被弹出过队列了？此时不就没法重新update了吗，而只能重新入队？作者回复: 已经出队的，就不会被重新update了的。
2019-07-08
jm3640独立事件概率想不明白.假如样本总数是2，一个同时包含A和B 另一个不包含A和B 那直接算样本同时包含A和B的概率是1/2。独立概率相乘就是1/2 * 1/2 = 1/4。请问我哪里理解错了作者回复: 你这个a b是啥啊
2019-07-02
收起评论
