找到最短长度的循环有向图具有正权重 [英] Find cycle of shortest length in a directed graph with positive weights
问题描述
有人问我，在接受记者采访这个问题，但我不能拿出任何像样的解决方案。所以，我告诉他们发现所有的循环再采摘周期用最少的长度幼稚的做法。
我很好奇，想知道什么是一个有效的解决这个问题。
您可以轻松地修改弗洛伊德算法。 （如果你不熟悉的图论可言，我建议检查出来，比如获得的介绍一个副本的算法）。
传统上，启动路径[I] [I] = 0 每个我。但是你可以而不是从路径[我] [我] =无穷大启动。这不会影响算法本身，因为这些零在计算中不使用呢（因为路径路径[I] [J] 永远不会改变的 K = =我或 K ==Ĵ）。
在最后，路径[I] [I] 是长度最短的周期经历我。因此，你需要找到分（路径[我] [我]）所有我。如果你想要周期本身（不只是它的长度），你可以做到这一点，就像它通常是与正常的路径：通过记忆 K 在执行算法。
此外，您还可以使用 Dijkstra算法找到一个最短的周期通过任何给定的节点。如果你运行这个改进Dijkstra为每个节点，你会得到相同的结果与弗洛伊德 - 沃肖尔。由于每个Dijkstra算法是为O（n ^ 2），你会得到相同的为O（n ^ 3）整体复杂性。
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.
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).
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).
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.
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屋！
