最短路径（Dijkstra算法和Floyd算法）

​ 在图中，不可避免要解决的一个问题就是计算两点之间的最短路径，对于图结构来说，两个点之间不一定只有一条路径，那么如何才能找出最短的那一条就是图中最短路径问题。最短路径问题在实际生活中应用十分广泛。接下来主要介绍两种较为常用的最短路径算法— D i j k s t r a Dijkstra Dijkstra算法和 F l o y d Floyd Floyd算法。

​ D i j k s t r a Dijkstra Dijkstra算法是一种较为经典的最短路径求解算法，它的整体思路和前面的 P r i m Prim Prim算法非常相似，但是又有一些不同之处。接下来首先对 D i j k s t r a Dijkstra Dijkstra算法的整体流程进行一个大致的了解：

从上述算法流程中可以看出， D i j k s t r a Dijkstra Dijkstra算法和 P r i m Prim Prim算法的相似之处在于在寻找路径时，都是逐点添加，添加之后也需要重新更新路径。

​ 该算法在计算的时候将所有的点分为两个集合，一个是目标点集 U U U，初始时只有起点， D i j k s t r a Dijkstra Dijkstra算法的功能是，给定一个起点，计算其到其他所有点的最短路径，也就是 1    t o    n 1\,\,to\,\, n 1ton的问题。之后在集合 T T T中找到起点 v 0 v_0 v0​能够达到的，且距离最短的点，将其加入到 U U U中，之后根据新加入的点，重新计算一次 v 0 v_0 v0​到 T T T中剩余点的当前最短距离即可。

​ 接下来通过一个例子来对该算法进行更进一步的理解。

​ 上述例子中，有图中圆圈中的字母代表节点的信息，圆圈上面的内容代表源点到其最短距离以及前驱节点，前驱节点用于后续重现最短路径。这里主要是使用到了一个简单的定理，**如果起点 v 0 v_0 v0​到目标点 u u u之间的某一条路径是最短路径，那么在该路径上面，任何一个点 u ′ u' u′到 v 0 v_0 v0​的路径都是 u ′ u' u′到 v 0 v_0 v0​的最短路径。**这个证明十分简单，使用反证法即可。那么这里在记录最短路径的信息时，如果需要重现路径中的顶点，那么只需要对于每一个结点设置一个前驱结点即可。

​ 接下来继续查看一个例子，这里使用表格的形式来对整个算法流程进行分析。

​ 在对该算法有了一定的理解之后，接下来就是考虑如何使用代码来实现它。由于该算法和 P r i m Prim Prim算法十分相近，所以在实现部分和 P r i m Prim Prim算法的实现部分基本一致，除了多了一个前驱数组，在初始化时，依旧是根据起点和邻接矩阵来对所有的距离进行初始化。对于源点到 T T T中点的最短距离，也是借助一个访问数组 v i s i t visit visit和距离数组 d i s dis dis来进行保存， v i s i t [ i ] = f a l s e visit[i]=false visit[i]=false代表第 i i i个点在集合 T T T中。之后在每次循环中，找出距离最短的，然后将其加入到集合 U U U中。最后就是最关键的一步，也就是根据新加入的点来更新到 T T T中剩余点的最短距离，这一步和 P r i m Prim Prim算法中的判断条件不同，需要注意。

​ 在具体实现路径重现的时候，主要是借助前驱数组和栈来进行实现，具体代码如下所示。