gpt4 book ai didi

algorithm - Floyd Warshall 算法在负权重循环上的时间复杂度

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:14:40 25 4
gpt4 key购买 nike

我知道当图中有负权重环时,没有找到最小距离的方法,也就没有最小距离的意义了。我的问题是,如果我们向 Floyd Warshall 算法提供具有负权重循环的图,会发生什么情况?它会在 O(n3) 内无限期地运行还是终止(也许答案错误)?

最佳答案

您可能会在 Wikipedia 上找到
Floyd-Warshall 算法中没有基于当前重量或最大重量的条件。
算法只是遍历所有顶点对并计算距离。所以答案是否定的,它不会无限期地运行。
并且算法肯定会返回错误的答案(对于负循环中的顶点,您将有负距离)。例如,从顶点到自身的距离将为负数。

此外,该算法还可以用于负循环检测。

关于algorithm - Floyd Warshall 算法在负权重循环上的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42907437/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com