数学和计算机科学板块_辛酸网

数据结构与算法14

  前面说的迪杰斯特拉算法是求一个起点到其它所有结点的最短路径用的算法。但现在换一个规模更大的问题：在一个图中要求出每一个结点到其它所有结点的最短路径，该怎么办？也就是说在n个结点的图里任取第i个和第j个结点，都能通过最优解的内容立刻知道最短路径是什么样子的。你应该怎么做？一直最简单的方式是在每一个结点的视角上分别套上迪杰斯特拉算法算法，反复n次。[doge]实际上RIP路由器算法就是这么干的，但实际上还有一种另外的方式——弗洛伊德算法。

  还是先看看上一次的那个图吧。

  画个邻接矩阵：

  邻接矩阵记载的是直接走的情况，但实际上的最短路径很有可能是有中转站的。借鉴一下先前求可达矩阵时的思路。我们对邻接矩阵做出修改，使其能够记录下当前已知最短的路径有多短，这样一来不难发现：矩阵中第i行写了i号结点出发到其它每一个结点的已知最短的路径有多短，而第j列写了从其它结点出发去往j号结点时已知最短的路径有多短。

  我们找到了i号结点到k号结点最短路径，以及k号到j号结点的最短路径，两个连起来是否一定是i号结点到j号结点的最短路径呢？不一定，因为整体上i号到j号结点的最短路径，不一定非要经过k号结点。但如果我们设置一个限制条件：必须经过k号结点，那么所得的最短距离一定大于等于不要求经过k号结点时的最短距离。因为前者有了限制条件，更加严格。即i号到j号的所有路径肯定满足：

  再引入一个可能的中转站m号结点，应该有：

  这些结点毕竟是可以编号的嘛，条件严格(n-2)点点，就是：

  反过来写：

  限制条件颠倒就是：

  邻接矩阵对应于“必须直达”，那要是允许A作为中转站呢？把矩阵第0列和第0行搬出来，分别取其中第i和j个数，我们可以找到一条i号结点→A→j号结点的路径，两数相加就是其距离。看看是不是比矩阵中i行j列那个小，若是小了就代替之。

  请看，选取2行3列之数，也就是C到D的路径,发现是9，更新之。这一轮干完以后便是：

  这里面已经用中转站A优化过了，接下来开放结点B的中转站作用。取第1列第1行作为核心，看看在允许AB作为中转站的情况下，最短距离会被优化成什么样子：

  最后结果我就不写了，太费手了。

  总体上，弗洛伊德算法的大体思路是：
  只允许0号结点作为中转站，更新距离
  只允许0,1号结点作为中转站，更新距离
  只允许0,1,2号结点作为中转站，更新距离
  ...
  只允许0~(n-2)号结点作为中转站，更新距离
  只允许0~(n-1)号结点作为中转站，更新距离


  矩阵写法就是：

   令k从0到n-1表示允许的中转站最大编号：
    令i从0到n-1表示起点编号：
     令j从0到n-1表示终点编号：
      如果矩阵【i行k列与k行j列上的数之和】小于【i行j列的数】，替代

  该算法的时间复杂度为O(n₃)

辛酸网 ©版权所有