gpt4 book ai didi

algorithm - 找到(稀疏)图直径的好算法?

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

我有一个大的、连通的、稀疏的邻接表形式的图。我想找到两个尽可能远的顶点,即 diameter of the graph以及实现它的两个顶点。

对于不同的应用程序,我对无向和有向情况下的这个问题都很感兴趣。在有向的情况下,我当然关心有向距离(从一个顶点到另一个顶点的最短有向路径)。

是否有比计算所有对最短路径更好的方法?

编辑:我所说的“尽可能远”当然是指“最长最短路径”——也就是说,从一到最短距离的所有顶点对中的最大值另一个。

最佳答案

好吧,我对这个问题进行了一些思考,并进行了一些谷歌搜索,很抱歉,但我找不到任何似乎不是“只找到所有对”的算法最短路径”。

但是,如果您假设 Floyd-Warshall 是计算此类事物的唯一算法(|V|^3 的 Big-Theta),那么我有一些好消息要告诉您:Johnson 的稀疏图算法(谢谢你,可信赖的 CLRS!)计算 (Big-Oh (|V|^2 * lgV + VE)) 中的所有对最短路径,这对于稀疏图应该渐近更快。

维基百科说它适用于定向(不确定无向,但至少我想不出不这样做的原因),这里是 link .

关于图表还有什么可能有用吗?如果它可以很容易地映射到 2D 平面上(因此,它的平面和边缘权重服从三角形不等式 [它可能需要满足更严格的要求,我不确定])你可能会打破一些几何算法(凸包可以在 nlogn 中运行,从那里找到最远的点对很容易)。

希望对您有所帮助!- 阿戈尔

编辑:希望链接现在有效。如果没有,只需谷歌它。 :)

关于algorithm - 找到(稀疏)图直径的好算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1190543/

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