最短路径(Dijsktra算法、Floyd算法)
1、最短路径:
两个结点之间,带权路径长度最短的路径。
常用算法是Dijkstra算法和Floyd算法,区别在于Dijsktra算法每次只能算出某一个结点到其他结点的最短路径,而Floyd算法可以直接把图中任意两个结点的最短路径都算出来。
最短路径一定是简单路径。
2、Dijkstra(迪杰斯特拉)算法
a、利用了三个数组
dist [ ] 表示距离源点的距离
path [ ] 记录现在结点的上一个结点
s [ ] 记录该结点有没有被访问过
b、无论用邻接矩阵还是邻接表存储,时间复杂度都为O(|V|2)
c、边上带有负权值时,不能使用Dijkstra算法。
d、每次都从中找未被访问过的距离源点最近哪个结点(比如离A最近的C),然后以这个结点(C)为中心,看这个结点(C)指向哪些其他的结点(E、F),然后更新这些结点(E、F)的值(就是如果加起来的值比原来的要小,则更新,说明找到更短的路径)。然后再从未访问的结点中,选取离源点最近的值,重复以上操作。等到所有结点都访问过后,最后一轮得到的就是所有其他结点到源点的最短路径长度。
e、答题的时候,一般要求把最后一轮得到的表写下来,根据这个表可以得到源点到其他结点最短路径长度,以及中间经过哪些结点。下图为一个例子:
3、Floyd(弗洛依德)算法
a、Floyd算法可以允许图中带有负权值的边,但是不能有带负权值的边组成的回路。
b、时间复杂度是O(|V|3),因为把建立临界矩阵需要遍历一遍,再一次轮流把经过每一个结点(第二遍),到达其他所有的结点(第三遍)的距离与现在的距离比较,如果更小则更新。
c、原理:
d、最终得到的表如何看最短路径和路径上经过的序列是多少:
下图为例子:比如a15,就是从1结点到5结点最短距离是60,从P矩阵可以知道,经过了4结点,即1 — 4 — 5,再看1,4之间,没有其他结点,4,5之间,又经过3结点。这样依次找下去,就可以得到路径。