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结点。这样依次找下去,就可以得到路径。

版权声明:本文为oaoa原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/oaoa/p/13749452.html