最短路径：地图软件是如何计算出最优出行路径的？

　　------ 本文是学习算法的笔记，《数据结构与算法之美》，极客时间的课程 ------ 　　今天，从地图软件的路径规划问题讲起，带你看看常用的最短路径算法（Shortest Path Algorithm）。 　　像 Google 地图。百度地图、高德地图这样的地图软件，应该会经常使用吧？如果从家开到公司，你只需要输入起始地址、结束地址，地图就会给你规划一条最优路线。这里的最优，有很多种定义，比如最短路线、最少用时路线、最少红灯路线等等。作为一名软件开发工程师，你是否想过，地图软件的最优路线是如何计算出来的吗？底层依赖了什么算法？ 　　我们刚提到的最优问题包含三个：最短路线、最少用时和最少红灯。我们先解决最简单的，最短路线。 　　解决软件开发中的实际问题，最重要的一点是建模，也就是将复杂的场景抽象成具体的数据结构。针对这个问题，我们该如何抽象成数据结构呢？ 　　我们之前也提到过，图这咱结构的表达能力很强，显然，把地图抽象成图最合适不过了。我们把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就在两顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。 　　具体的代码实现，我放在下面了。于是，我们要求解的问题就转化为，在一个有向有权图中，求两个顶点的最短路径。 　　想要解决这个问题，有一个非常经典的算法，最短路径算法，更加准确地说，是单源最短路径算法&#