在具有正权重的有向图中找到最短长度的环 [英] Find cycle of shortest length in a directed graph with positive weights

问题描述

我在一次采访中被问到这个问题，但我想不出任何像样的解决方案.所以，我告诉他们找到所有循环然后选择长度最短的循环的天真方法.

I was asked this question in an interview, but I couldn't come up with any decent solution. So, I told them the naive approach of finding all the cycles then picking the cycle with the least length.

我很想知道这个问题的有效解决方案是什么.

I'm curious to know what is an efficient solution to this problem.

推荐答案

您可以轻松修改 Floyd-Warshall 算法.(如果您根本不熟悉图论，我建议您查看一下，例如获取一份 Introduction到算法).

You can easily modify Floyd-Warshall algorithm. (If you're not familiar with graph theory at all, I suggest checking it out, e.g. getting a copy of Introduction to Algorithms).

传统上，您为每个 i 开始 path[i][i] = 0.但是您可以改为从 path[i][i] = INFINITY 开始.它不会影响算法本身，因为无论如何这些零都没有用于计算(因为路径 path[i][j] 永远不会改变 k == i或 k == j).

Traditionally, you start path[i][i] = 0 for each i. But you can instead start from path[i][i] = INFINITY. It won't affect algorithm itself, as those zeroes weren't used in computation anyway (since path path[i][j] will never change for k == i or k == j).

最后，path[i][i]是经过i的最短循环的长度.因此，您需要为所有 i 找到 min(path[i][i]).如果你想要循环本身(不仅是它的长度)，你可以像通常使用普通路径一样完成它:通过在算法执行期间记住 k.

In the end, path[i][i] is the length the shortest cycle going through i. Consequently, you need to find min(path[i][i]) for all i. And if you want cycle itself (not only its length), you can do it just like it's usually done with normal paths: by memorizing k during execution of algorithm.

此外，您还可以使用Dijkstra's algorithm 来找到经过的最短循环任何给定的节点.如果您为每个节点运行此修改后的 Dijkstra，您将获得与 Floyd-Warshall 相同的结果.由于每个 Dijkstra 都是 O(n^2)，你将得到相同的 O(n^3) 整体复杂度.

In addition, you can also use Dijkstra's algorithm to find a shortest cycle going through any given node. If you run this modified Dijkstra for each node, you'll get the same result as with Floyd-Warshall. And since each Dijkstra is O(n^2), you'll get the same O(n^3) overall complexity.

这篇关于在具有正权重的有向图中找到最短长度的环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！