如果我必须在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 |？
likewindyaya 回答：描述最多运行时间为O（nm log n）的算法
是的，根据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 弧，并且没有负长度定向循环。