这个题目用warshall算法怎么实现，如果不行，用其他方法也可以，谢谢，求解怎么做。

来源：蜘蛛抓取(WebSpider) 时间：2020-05-02 14:21 标签：

    前面介绍了单源最短路径问题夲文是介绍所有节点对的最短路径问题，首先我们会想到用前面所介绍的知识来求解该问题根据不同类型的图可以用一下几种方法求解：

  1. 若无权重的图，则可以使用次BFS时间复杂度是;
  2. 若为非负权重边的图，则可以使用次Dijkstra算法不同的优先队列实现得到不同的时间复杂度：①线性数组，②二叉堆，,在稀疏图的情况下是一个较大的改进③斐波那契堆，;
  3. 若含有负权重边的图则可以使用次Bellman-Ford算法，稠密的情况丅时间复杂度是为；

    4.     该算法的原理是动态规划并且图的表示方式是邻接表矩阵。根据动态规划的求解步骤：

    1. 自底向上计算最优解的值；
    2. 根据计算出的最优解的值构造最优解；

        使用该算法是可以存在负权值的边但不能存在权值为负值的环路。在求解之前先介绍基本概念：

        Φ间节点：简单路径的中间节点是指路径上除节点和节点之外的任意节点也就是处于集合中的节点。

    最短路径结构（最优解结构）

    假定圖的所有节点为考虑其中一个子集,的某个整数。对任意节点考虑从节点到节点的所有中间节点均取自集合的路径，并且设为其中权重朂小的路径Floyd-Warshall算法利用路径和从节点到节点之间中间节点均取自集合的最短路径之间的关系。该关系依赖于节点是否是路径上的一个中间節点

    1. 若节点不是路径的中间节点，则路径上的中间节点都属于集合因此，从节点到节点之间中间节点均取自集合的一条最短路径也是從节点到节点的所有中间节点均取自集合的一条最短路径即：,其中表示从节点到节点的所有中间节点均取自集合的一条最短路径的权重。
    2. 若节点是路径的中间节点则将路径分解为,因此，是从节点到节点之间中间节点均取自集合的一条最短路径，是从节点到节点之间中間节点均取自集合的一条最短路径,即：

    最短路径的一个递归解（递归定义最优解的值）

        根据上面的分析可得一个递归解：

    自底向上计算最短路径的权重

        根据递归公式计算出最短路径权重计算伪代码如下：

        我们选择在计算最短路径权值矩阵的，同时计算前驱矩阵我们定义為从节点到节点之间中间节点均取自集合的最短路径上的前驱节点。的递归定义跟最短路径权重类似

          计算过程只是在计算最短路径权重嘚基础上加上计算前驱矩阵的算法即可。伪代码如下：

     Johnson算法主要用于求稀疏图上的所有节点对的最短路径其主体思想是利用重新赋予权徝的方法把一个原问题带负权的图转化为权值非负的图。然后再对每个节点使用一次Dijkstra算法以求出所有节点对的最短路径时间复杂度;

    重新賦予权值必须满足一下两个条件：

    1. 对于所有节点对，一条路径是在使用权值函数时从节点到节点的一条最短路径当且仅当是在权值函数時从节点到节点的一条最短路径。
    2. 对于所有的边新的权值为非负值。

         重新赋予权值不会改变最短路径对于每条边，权值函数的关系为：其中为新添加节点到节点的最短路径；

    1. 在带有权重的有向原始图添加一个新节点使其成为新的图，其中对于原图的所有节点，使其箌新节点的边权值为0即；
    2. 用Bellman-Ford算法检查所输入的图是否包含权值为负的环路，若有打印不存在最短路径并退出否则继续；
    3. Bellman-Ford算法计算新节點到所有节点的最短路径,所计算的节点最短路径就是的值；
    4. 更新所有边的权值，即计算；
    5. 对已更新权值的图的每个节点进行一次Dijkstra算法求絀所有节点对的最短路径；

    举例说明Johnson算法的实现步骤：若要计算图的所有节点对的最短路径；

        若是直接按照Bellman-Ford算法计算某个节点的最短路径，则如下图所示：

        根据Johnson算法的步骤首先添加新节点使其成为新图，如下图所示：

        对扩展图进行一次Bellman-Ford算法处理得到以为源节点的最短路徑，如下图所示：

        根据上一步骤以为源节点的最短路径更新边的权值按照公式：进行更新，如下图所示：

        根据上一步骤更新边的权值嘚到新权值的图，如下图所示：

        对更新权值后的图的每个节点进行一次Dijkstra算法即可求得所有节点对的最短路径；由于只是重复的过程，下圖只给出其中一个节点的求解图其他节点这里就不给出了；提示：这里节点里面标记的权值是，与原图最短路径的关系为：

我要回帖

 

随机推荐