gpt4 book ai didi

algorithm - 图中的最短路径

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

我有一个两部分的问题:

G=(V,E) 是无向无权图。 t,s 是图中的节点。 e=(a,b) 是图中的一条边。

1) 提出一个有效的算法来检查 e 是否是从 st 所有 最短路径的一部分em>.

2) 提出一个有效的算法来检查 e 是否是从 st 的一个最短路径的一部分.

我在论坛中看到了解决第 1 部分的建议,方法是两次使用 Dijkstra 算法,一次使用给定边,一次不使用。然后你需要比较结果。但是,我没有想出更有效的方法来解决第 2 节。我想这是可能的,但我不知道如何。

有什么建议吗?

最佳答案

实际上对于未加权的无向图,您不需要使用 Dijkstra,一个简单的 BFS 就可以达到目的

以下方法检查 e 是否是从 s 到 t 的至少一条最短路径的一部分:

计算s到e的最短路径和e到t的最短路径

如果这两条路径的长度之和等于从s到t的最短路径,则e是至少一条从s到t的最短路径的一部分。

s -----> e -------> t

如果你想知道 e 是否是从 s 到 t 的exactly one 最短路径的一部分,那么另外,以下链接可能会有帮助。它涉及一个有向图,但我们的无向图可以被认为是一个有向图,边从 u 到 vv 到 u

How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

关于algorithm - 图中的最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24167662/

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