#重要#图之最短路径

2019-08-24 本文已影响0人 mark_x

最短路径

最短路径就是指两个顶点之间经过的边上权值之和最小的路径。注意与最小生成树是有明显区别的。最短路径是从源点到终点怎么走最近，而最小生成树是如何用最短的距离连接图中所有的点。
求解最短路径有两种典型的算法：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