本文介绍一下的 单源最短路径算法个人解读

看了一些其他博文，感觉介绍的不是很清楚，本文用最通俗易懂的方法来解读；

本文采用定义式语言来解读，首先给出如下定义：

1，d(x,y): 任意2个节点x,y之间如果有一条加权边 则d(x,y)为权值，否则为+无穷；

2，m(x,y): 节点x,y之间的最短加权路径的加权距离 ,也就是x,y之间的最短加权距离；

3，N:所有节点的集合

4, a: 初始节点，将要计算该节点到其余所有节点距离；

5, S:状态变量，记录当前已经计算出的到a的最短加权距离的节点集合，初始为{a}

现在我们想办法扩大S:

首先，遍历N\S中的所有节点，对其中每一个节点x ,做如下事情：

遍历 S中的节点s, 计算 m(a,s)+d(s,x);  并求出其中最小的值  ，这个最小值

只与a,S和x有关，记为 m(a,S,x)

对于N\S中的所有节点x,找出x'（如果不唯一随意取其中一个）使得m(a,S,x)在x=x'时取最小值，

那么此时可以断言，m(a,x')=m(a,S,x') ;

证明： 假设m(a,x')!=m(a,S,x')，

因为m(a,S,x')对应的值 是:   a不经过N\S-{x'}中的任何节点直接到达x'的最小加权距离；

如果它！=m(a,x') ， 就意味着 存在一条从a到x'并经过N\S-{x'}中某点的路径有更小的距离,

不妨设这条路径为path,a沿着path走到x'中第一次出现的不在N\S中的点为p,

那么这条路径的加权距离 > m(a,S,p)>=m(a,S,x') ，矛盾；

证明完毕；

因此 ，我们求出了m(a,x')，把x'加入S 得到一个比S更大的集合，

重复这个过程可以求出，所有单源最短路径！