狄克斯特拉算法(Dijkstra )
用于计算出不存在非正权重的情况下，起点到各个节点的最短距离。
思路：
1.从起点开始，计算起点到各个节点耗时，并更新各节点的耗时。
2.找到各节点耗时最小的节点A，计算A节点到相邻节点的耗时，并更新相邻节点的耗时。
3.将A标记为已处理。
4.重复2，3。
示例：
广度优先1.jpg
解析：
1.起点A开始，可到达B,E,F三个节点，更新耗时1,4,8。
2.B,E,F中，B耗时最短，开始处理B
3.更新节点C,G,F，分别为3,7,7。
4.E,F,C,G中，C耗时最短，开始处理C，
5.直到所有点处理结束。
广度优先2.jpg
最短路径为：
A:
B:A->B
C:A->B->C
D:A->B->C->D
E:A->E
F:A->B->C->G->F
G:A->B->C->G
H:A->B->C->G->H
伪码
Dijkstra.jpg
贝尔曼-福特算法(Bellman–Ford algorithm )
用于计算出起点到各个节点的最短距离，支持存在负权重的情况。原理是对图进行最多V-1次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。
思路：
1.所有点的初始化距离为∞，列出所有的边。
2.从起点开始，遍历所有的边，对每条边进行松弛操作。
3.重复过程2，直到相比上一次，所有点的距离都没有改变位置，最多进行n-1次重复(n为节点数)。
所谓的松弛，以边ab为例，若dist(a)代表起点s到达a点所需要花费的总数，dist(b)代表起点s到达b点所需要花费的总数,weight(ab)代表边ab的权重，
若存在:(dist(a) +weight(ab)) < dist(b)
则说明存在到b的更短的路径,s->...->a->b,更新b点的总花费为(dist(a) +weight(ab))，父节点为a
示例：
广度优先3.jpg
第一次遍历
广度优先4.jpg
第二次遍历
广度优先5.jpg
第二次遍历相比第一次遍历，并没有改变任何节点，计算结束。
得到结果：
B:A->B,4
C:A->C,-2
D:A->C->D,0
F:A->C->F,-1
G:A->B->H->G,1
H:A->B->H,0
I:A->B->H->G,0
伪码
Bellman-Ford.jpg
网友评论