gpt4 book ai didi

algorithm - 负权重的 Dijkstra

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

我正在尝试找到一个具有负权重(没有负循环)的有向图的示例,以便在其上运行 dijksra 会对图中的所有顶点产生错误的结果(除了源节点)。

不难找到 dijkstra 生成的某些结果错误的图表示例。但我找不到上述图表的示例,任何人都可以帮助我吗?

谢谢。

最佳答案

假设您有一个包含三个节点 A B 和 C 的图 G。三弧 (A,B,5) , (A,C,2) , (B,c,-10)来源是A。

现在从 A 到 C 的最短路径将是 2,这是错误的。

应该是-5。

关于algorithm - 负权重的 Dijkstra,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39322324/

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