复习

在我们之前的学习之中,已经了解三种不同的最短路径算法,他们在某些条件限制下拥有不同的性能

  • 无权图 或者说权重全部相同 可以使用 广度优先搜索(借助FIFO)
  • 无负权图 可以使用 Dijkstra算法
  • 有负权或者可能出现负环 可以使用bellman-ford算法

接下来我们将迎来更大的挑战。

全点最短路径算法

所谓全点最短路径,就是求图中所有的点到另外所有点到最短路径。

本能的,我们最先想到解决这个问题的办法就是利用我们上面提到的单源最短路径算法运行V遍。

可以用图都特性一一对应上面的算法 其实无权图和无负权图他们利用上面算法运行v遍的性能还是可以接受的,因为他们本身都是或者接近线性时间的算法,顶多也就是升级成多项式。最垃圾的就是上面的第三张,负权图,O(V^2*E),相当高成本了,所以我们需要一些更好的时间来解决这些问题。我们将会得到三种更好的算法来解决上面的三种图类型中的全点最短路径问题。

清晰问题

为了方便描述与研究,我们对该问题进行表述

拥有图 G = (V,E) 我们将图中的所有节点V 表述成 {1,2,3,4,…n} 权重函数W 输出:一个n*n的矩阵Δ 其中Δ(i,j)就是从i到j底最短路径总权重

算法1

引导

首先我们建立一个权重矩阵A A(i,j)中包含了i到j底权重(如果ij连接的话) 定义 d(i,j)(m) 代表了从点i到点j到最短路径的权重。并且拥有一个限制条件m 即i到j最多用m条边达到 引出 d(i,j)(0) = i === j ? 0 : +infinite 也就是说如果规定两点最短路径权重为0 那么这两点只能是同一个点,否则不可能连接(忽略负权重)

看的太懵了,挖个坑吧,以后再填。暂时搁置