最短路径
最短路径就是指两个顶点之间经过的边上权值之和最小的路径。注意与最小生成树是有明显区别的。最短路径是从源点到终点怎么走最近，而最小生成树是如何用最短的距离连接图中所有的点。
求解最短路径有两种典型的算法：Dijkstra算法和Floyd算法。
迪杰斯特拉(Dijkstra)算法
1.1 基本原理
其基本思想与Prim的思想很像，都是基于贪婪算法的思想，不断地选择局部最优的点，从而得到的结果就是全局最优。
Dijkstra算法
首先证明一个问题：假设已经找出从0号顶点到4号顶点的最短路径为黄线，即0→1→7→8→2→5→4，那么这条路径也是到路径上其他点的最短距离，也就是说0号顶点到8号顶点的最短路径就是0→1→7→8。
采用反证法：
前提：0→1→7→8→2→5→4是0到4的最短路径
证明：0→1→7→8是0到8的最短路径
假设命题不真，0到8的最短路径是其他路径，比如0→1→7→6→8。那么可以推出0→1→7→8→2→5→4不是0到4的最短路径，与前提矛盾，因此假设不成立，原命题为真。
那么，根据这一结论，只需要从源点出发，一步步找出临近顶点的最短路径，直到到达4，那么这条路径就是0到4的最短路径。
与Prim算法类似，将图分为两个集合，已经在最短路径上的点集A和未归入的点集B。每加入一个点，就更新源点到所有点的距离，然后选择最短的一条，加入→更新→选择最小，如此循环，直到到达终点为止。
1. 2 视频
视频1：(熟肉)Dijkstra算法详解，轻松入门——Youtube
这个视频很棒！！重点看！
视频2：图论最短距离(Shortest Path)算法动画演示
1.3 代码关键点说明
总体思路就是：更新→搜索最短点→加入该点
通过三个数组实现：visited[]、minDist[]、parent[]。
visited[]数组初始化为0，表明还没有顶点加入最短路径；
minDist[]数组初始化为INF，表明源点与所有点的距离都是无穷大；
parent[]数组初始化为-1，在某个点加入时，将其父亲顶点记录下来；
说明一下过程：
初始化：
选择0号顶点作为源点，并加入路径。visited[] = {1, 0, 0, 0, 0, 0, 0, 0, 0}，minDist = {0, INF, INF, INF, INF, INF, INF, INF, INF}
循环：
更新：
利用邻接矩阵G的第0行，找到与0号顶点相连的顶点，并将minDist[]更新为较小值；
Dijkstra.gif
以第二次循环为例，1号顶点新加入，因此更新0号顶点到2、7号顶点的距离。计算通过该点到达2、7号顶点的距离，该值小则更新为该值，如果该值大，则保持minDist对应元素不变。
如图cal-2 = 4+8 < INF，更新minDist[2] = 12，cal-7 = 4+3 = 7 < 8，同样更新minDist[7] = 7。
因为这些顶点都与0号顶点相连，所以更新parent[]对应下标位置的值为0，说明这新点的父亲结点是0号顶点。
搜索最小值：在未访问顶点中找minDist最小的顶点。
选择：该顶点加入最短路径。
循环结束后，根据minDist[]可以知道源点到各个顶点之间的最短路径，通过parent[]可以描画出最短路径。
1.4 代码
Graph/Dijkstra_ShortestPath.c
弗洛伊德(Floyd)算法
1.1 基本原理
Floyd算法是一种动态规划算法，通过循环迭代的方式向最优解靠近。
Floyd算法
如图所示，该算法基于以上两个结论，使用数组D和S实现一次计算得到图中任意两个点之间的最短距离。
矩阵D反映任意两个点之间的距离，用邻接矩阵直接初始化。也就是说，最初的D就是邻接矩阵G.arc[][]。该矩阵的作用与之前minDist数组类似。
矩阵S反映顶点的前后关系，与之前的parent[]数组的作用类似。初始化的S如下所示。
D矩阵与S矩阵
初始化的S中，元素的值都与列数相同，说明对应的D矩阵距离是直接距离，即不经过任何一个点的中转。
从0号顶点开始循环，判断D中两点之间的距离通过顶点0的中转是否会更小，如果是，则更新D中的值为较小值，同时修改S对应位置为0，说明这一距离是通过0号顶点中转得到的。
比如初始情况下3号顶点到1号顶点没有联系，即距离为无穷大，但通过0号顶点中转后，其距离减小为2+3=5。
当循环结束后，相邻两个点之间的距离都是最优的，那么根据S矩阵的指示，任意两点之间通过局部最优路径连接起来的路径也是最优的。
1.2 视频
视频1：图论最短距离(Shortest Path)算法动画演示
1.3 代码
Graph/Floyd_ShortestPath.c
网友评论