导航软件如何规划ampampquot最短路线ampampquot？

　　程序员视角科普生活知识
　　hello 大家好
　　我是浩说
　　关于＂最短路线＂这个问题
　　我们生活中有一个典型应用：
　　使用导航软件帮我们规划从 出发地 到 目的地 的最短路线
　　今天我们就来研究一下：导航软件如何计算＂最短路线＂
　　抽象
　　首先我们需要将导航软件中的地图抽象成一种数据结构：图
　　关于 图 的介绍，我用一张图片做简单说明
　　图 的更多详细内容兄弟们可以过一下我之前的文章
　　于是我们可以这样对应：
　　顶点 > 地图上的路口
　　边 > 两个路口间的道路
　　入度和出度 > 道路的方向
　　边的权重 > 两个路口间的距离
　　按照上面的思路我们抽象成图就是这样的：
　　数据结构是为算法服务的，我们将地图抽象成数据结构 图 之后，
　　下一步就是在该数据结构上设计出一种算法来计算出最短路线。
　　点个赞，证明你还爱我
　　算法
　　针对求＂最短路径＂的场景，有一种经典的算法叫做：
　　＂Dijkstra 算法＂ 由荷兰计算机科学家 Edsger Wybe Dijkstra 在1956年发现
　　这也就是我们本篇的重点了，
　　算法问题很难用一两句话解释清楚，所以接下来我将分步骤拆解＂应用Dijkstra 算法计算最短路径＂的过程，
　　大家需要从过程中感受和体会Dijkstra 算法的思路和原理。
　　先将图中每个顶点用编号表示，目标就是计算顶点1到8的最短距离
　　接着我们准备两个数组：
　　一个数组存放图中除起点以外的所有顶点 V = {2，3，4，5，6，7，8}
　　另一个数组先存放起点 S = {1}
　　我们以起点1为原点，逐步统计其它顶点到原点的距离，无法直接到达的顶点距离用/表示
　　1
　　统计结果如下：
　　dist 1-2：270
　　dist 1-3：300
　　dist 1-4：/
　　dist 1-5：200
　　dist 1-6：/
　　dist 1-7：/
　　dist 1-8：/
　　然后通过比较上面的结果选择最小的值，也就是dist 1-5，至此 ＂Dijkstra 算法＂会暂时认定：
　　顶点1 到5 的最短距离为200。
　　此时将顶点5从数组V中移除，并添加至数组S：
　　V = {2，3，4，6，7，8}
　　S = {1，5}
　　所以数组S中的顶点其实就是表示＂已经找到从原点到对应顶点的最短距离＂的顶点集。
　　经过此步骤后， ＂Dijkstra 算法＂暂时认定找到了从原点1至顶点5的最短路径，我们用绿色表做标记。
　　2
　　该步骤与上一步逻辑相同，但区别在于：
　　由于我们找到了到达顶点5的最短路径，所以之前无法到达的顶点(4、6)，在该步骤就可以通过顶点5间接的到达了
　　于是再次统计距离
　　dist 1-2：270
　　dist 1-3：300
　　dist 1-4 > 1-5 （200） + 5-4（260）：460
　　dist 1-5：200
　　dist 1-6 > 1-5 （200） + 5-6（310）：510
　　dist 1-7：/
　　dist 1-8：/
　　除去已经被加入到数组S中的顶点，我们依然从剩下的距离中选出最短的，然后将该顶点从数组V移除并加入数组S
　　V = {3，4，6，7，8}
　　S = {1，5，2}
　　看到这里相信大家已经对＂Dijkstra 算法＂的逻辑有点感觉了，我们不妨简单梳理一下：
　　＂Dijkstra 算法＂需要准备两个数组，一个存放从起点至终点涉及到的所有顶点，另一个存放已经确定最短路径的顶点，
　　然后从原点开始，循环查找至下一顶点距离最短的顶点并将其从V移除然后添加至S中，直至V中顶点全部添加至S中。
　　当然，这其中还有一些细节需要注意，我们继续往下看。
　　3
　　细节来了，注意看这里的顶点4，由于前两步我们打通了顶点2、5的最短距离，因此到达顶点4的路径有两条：
　　dist 1-4 >
　　1-5 （200） + 5-4（260）：460
　　1-2 （270） + 2-4（210）：480
　　而此时＂Dijkstra 算法＂将取距离小的作为最终结果。
　　最终统计的距离
　　dist 1-2：270
　　dist 1-3：300
　　dist 1-4 > 1-5 （200） + 5-4（260）：460
　　dist 1-5：200
　　dist 1-6 > 1-5 （200） + 5-6（310）：510
　　dist 1-7：/
　　dist 1-8：/
　　距离最短的顶点为3：
　　V = {4，6，7，8}
　　S = {1，5，2，3}
　　4
　　这一步顶点6和上一步顶点4出现了一样的情况，
　　由于我们打通了顶点3，所以到达顶点6的路径变成了两条
　　dist 1-6 >
　　1-5 （200） + 5-6（310）：510
　　1-3 （300） + 3-6（180）：480
　　依然选择距离短的作为最终结果。
　　dist 1-2：270
　　dist 1-3：300
　　dist 1-4 > 1-5 （200） + 5-4（260）：460
　　dist 1-5：200
　　dist 1-6 > 1-3 （300） + 3-6（180）：480
　　dist 1-7：/
　　dist 1-8：/
　　顶点4加入S：
　　V = {6，7，8}
　　S = {1，5，2，3，4}
　　看到这一步相信大家对＂Dijkstra 算法＂的逻辑和一些细节已经有了大体的感受，后面的步骤就很好理解了，我们继续往下看。
　　5
　　dist 1-2：270
　　dist 1-3：300
　　dist 1-4 > 1-5 （200） + 5-4（260）：460
　　dist 1-5：200
　　dist 1-6 > 1-3 （300） + 3-6（180）：480
　　dist 1-7 > 1-4 （460） + 4-7（130）：590
　　dist 1-8：/
　　顶点6加入S：
　　V = {7，8}
　　S = {1，5，2，3，4，6}
　　6
　　dist 1-2：270
　　dist 1-3：300
　　dist 1-4 > 1-5 （200） + 5-4（260）：460
　　dist 1-5：200
　　dist 1-6 > 1-3 （300） + 3-6（180）：480
　　dist 1-7：1-4 （460） + 4-7（130）：590
　　dist 1-8：1-6 （480） + 6-8（100）：580
　　V = {7}
　　S = {1，5，2，3，4，6，8}
　　7
　　dist 1-2：270
　　dist 1-3：300
　　dist 1-4 > 1-5 （200） + 5-4（260）：460
　　dist 1-5：200
　　dist 1-6 > 1-3 （300） + 3-6（180）：480
　　dist 1-7：1-4 （460） + 4-7（130）：590
　　dist 1-8：1-6 （480） + 6-8（100）：580
　　V = {}
　　S = {1，5，2，3，4，6，8，7}
　　到这一步数组V已经为空，＂Dijkstra 算法＂就到此结束了。
　　兄弟们可能会有疑问，因为在下图中，由顶点7至顶点8这条路线并没有做判断，难道是＂Dijkstra 算法＂有问题吗？
　　我们回看一下刚才距离的计算结果
　　dist 1-7：1-4 （460） + 4-7（130）：590
　　dist 1-8：1-6 （480） + 6-8（100）：580
　　既然dist 1-7已经大于dist 1-8，
　　那么dist 1-7  + dist 7-8 必然是会大于dist 1-8的，所以这是符合逻辑的，无需再判断了。
　　到这里＂Dijkstra 算法＂就成功的帮我们规划出了最短路线：
　　dist 1-8 > 1-3 （300） + 3-6（180） + 6-8（100）：580
　　听说好看的人都点赞分享了哦！