最多描述O(nm log n)运行时间的算法

问题描述 投票:-2回答:1

[如果必须在O | V | 3 |中给出算法,它以边长为正的有向图作为输入,并返回图中最短周期的长度(如果图是非循环的,则应这样说)。我知道它将是:令G为图,定义一个矩阵Dij,它存储对任意一对顶点u,v从顶点i到j的最短路径。 u和v之间可能有两条最短的路径。周期的长度为Duv + Dvu。这样就足以对任何给定的u和v对顶点进行Duv + Dvu最小化。

我是否可以这样写,使其最多为O(nm log n)(其中n是顶点数,m是边数),而不是O | V | 3 |?

algorithm
1个回答
0
投票

是的,根据Orlin和Sedeño-Noda(2017)题为An O(nm) time algorithm for finding the min length directed cycle in a graph的会议论文,实际上这个问题可以在O(nm)中解决。

在本文中,我们引入了O(nm

)时间算法,以确定具有n节点且< [m弧,没有负长度有向循环。
© www.soinside.com 2019 - 2024. All rights reserved.