[Algorithm_Learn_01]单源最短路径

序

工作后一直都处于高压状态，现实生活把理想压的快喘不过气来，有时候很压抑、很累，没有理想的生活让人厌恶。

在学校的时候就想学学算法，一直没有投入进去，这次又突然燃起了兴趣，不管能不能坚持下去，反正此刻是真的做了自己想做的事，就在这里展开理想吧。

1. 最短的路线

在了解这个算法前，先来看一个问题。

图上的城市之间的连线代表有道路可达，数字代码两城市之间的距离。那么从城市A出发，选择哪条路线才能最快到达城市D？最短的距离是多少？

要求出这个问题的答案并不难，只要罗列出从A到D的所有道路并计算出距离之和，结果是显而易见的，A→B→C→D 是最佳路径。

A→B→C→D ： 5

A→B→C→F→E→D ： 12

A→F→E→D ： 6

A→F→C→D ： 7

但这显然不是我们想要的，假如我们要计算深圳到哈尔滨之间的最短路径，中间有无数的城市和道路，这时候如果还是用上面穷举的方法，谁都会疯掉的吧。

除了穷举，能不能找出一个一般性的方法，用程序来实现呢？

2.除了穷举，可以做的更好

用上面那张地图来设计出程序显然是很难的，所以，我们要做的第一件事情就是把这张地图变成方便计算的数据。

（1）矩阵

准确的说，是邻接矩阵，叫什么不重要，关键是干什么。

矩阵中的每一个元素代表两个城市之间的距离，不相邻的两个城市之间的距离为无穷大（∞）。

邻接矩阵

	A	B	C	D	E	F
A	0	1	∞	∞	∞	2
B	1	0	3	∞	∞	∞
C	∞	3	0	1	∞	4
D	∞	∞	1	0	3	∞
E	∞	∞	∞	3	0	1
F	2	∞	4	∞	1	0

A→B的距离为1，那么A行B列的元素和B行A列的元素取值都为1；

A与C不相邻，故A行C列和C行A列都为无穷大；

各城市自己到自己的距离都为0。

这样，只需要通过一个二维数组就可以把这张地图的信息记录下来。

（2）路在何方

做好了准备工作，开始求取点A到点D的最短距离。

以矩阵的第一行作为初始状态，填入下表中。表中的行为地图上的点，列表示操作序号，表格中的每个单元代表A点到该点的最短距离。

上面的矩阵中我们只给出了相邻两点之间的距离，不相邻的点的距离都被设为无穷。现在的目的就是要求出这些无穷的真实距离。

	A	B	C	D	E	F
I	0	1	∞	∞	∞	2
II	0	1	4	∞	∞	2
III	0	1	4	∞	3	2
IV	0	1	4	6	3	2
V	0	1	4	5	3	2

（表中绿色方格代表已经标记的点，蓝色代表下次寻路的基点）

步骤：

1）从矩阵中得到A点到各点的距离，填入表中。找出距A点最近的点，即点B。标记点B，作为下次寻路的基点，并将点B从待确认点中剔除；

2）当前基准点为点B，重新计算各点到点A的距离，得到点C。找出未确认点中距点A最近的点，即点F，标记，并从未确认点中剔除；

3）重复上述工作，不再赘述。共需N-1个步骤（5步）可以计算出A点到D点的最短距离。其实，表中最后一行即是A点到图中任意一点的最短距离。

注意：

1）在第四行中A点到D点的最短距离为6，而第五行中为5。而被标记过的点（从未确认集合中剔除的点）到A点的距离不会再变化。这说明该方法是不需要回溯的，已经确认的即是最好的。

2）表中只体现了A点到各点的最短距离，却无法看出到各点的最短路线。因此，需要在更新各点距离的时候，记录下到该点的线路。下图中是点A到各点的最短路线的寻找过程。

3.Dijkstra算法

在这一节里，将上面讨论的方法抽象出来，也就是Dijkstra算法。

Dijkstra算法，以荷兰计算机科学家Edsger Wybe Dijkstra（艾兹格·W·迪科斯彻）命名。是一个很经典的最短路径求解方法。

Dijkstra算法的几个关键点：集合、贪心算法、松弛技术。有了上文的描述，这里再用上几张图，理解这个算法还是很容易的。

1、集合：算法中用到了两个集合S和U，与起点之间最短距离确定的点被放在集合S中，未确认的点放在集合U中。

2、贪心算法：每次加入到集合S中的点都是集合U中距起点最近的点。

3、松弛技术：每一步迭代中，重新计算集合U中的点与起点之间的距离d_new，如果d_new小于之前记录的距离d_min，则更新d_min = d_new。

待续……