gpt4 book ai didi

dijkstra - 为什么我们不能将 Dijkstra 算法应用于具有负权重的图?

转载 作者:行者123 更新时间:2023-12-04 13:08:59 24 4
gpt4 key购买 nike

为什么我们不能将 Dijkstra 算法应用于具有负权重的图?

最佳答案

如果每次从 C 到 D 旅行都得到报酬,那么找到从 A 到 B 的最便宜的路径意味着什么?

如果两个节点之间存在负权重,则“最短路径”将永远在这两个节点之间向后和向前循环。跳数越多,路径就越“短”。

这与算法无关,与无法回答这样的问题有关。

编辑 :

上述声明假定双向链接。如果没有整体负权重的周期,你就没有办法永远循环,获得报酬。

在这种情况下,Dijkstra 算法可能仍然失败:

考虑两条路径:

  • 在穿过权重为 -25 的最终边之前,成本为 100 的最佳路径,总共为 75,并且
  • 没有负加权边的次优路径,总成本为 90。

  • Dijkstra 算法将首先调查次优路径,并在找到时宣布自己已完成。它永远不会跟进比找到的第一个解决方案更糟糕的子路径

    关于dijkstra - 为什么我们不能将 Dijkstra 算法应用于具有负权重的图?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3200446/

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