我正在寻找一种算法，该算法采用有向加权图(具有正整数权重)并找到图中具有最小平均权重(而不是总权重)的循环。
基于类似的问题(但针对总权重)，我考虑应用 Floyd–Warshall 算法的修改版，但它将依赖于以下属性，该属性不成立(谢谢 Ron Teller 提供了一个反例来证明这一点):“对于顶点 U,V,W，如果存在从 U 到 V 的路径 p1,p2，以及从 V 到 W 的路径 p3,p4，那么这些路径的最优组合可以得到从 U 到 W 是 p1,p2 中较好的，其次是 p3,p4 中较好的。"
我还可以考虑哪些不依赖此属性的其他算法？
编辑:将不再相关的以下段落移至问题下方。
While this property seems intuitive, it doesn't seem to hold in the case of two paths that are equally desirable. For example, if p1 has total weight 2 and length 2, and p2 has total weight 3 and length 3, neither one is better than the other. However, if p3 and p4 have greater total weights than lengths, p2 is preferable to p1. In my desired application, weights of each edge are positive integers, so this property is enforced and I think I can assume that, in the case of a tie, longer paths are better. However, I still can't prove that this works, so I can't verify the correctness of any algorithm relying on it.
最佳答案
"While this property seems intuitive, it doesn't seem to hold in the case of two paths that are equally desirable."
实际上，当您考虑 2 个参数(重量、长度)时，它在任何情况下都不成立，这里有一个示例，当 P1 本身的平均值小于 P2 时，有时可能会更好(示例 1)最终解决方案或更差的解决方案(示例 2)，取决于 P3 和 P4。
示例1:
L(P1) = 9, W(P1) = 10
L(P2) = 1, W(P2) = 1
L(P3) = 1, W(P3) = 1
L(P4) = 1, W(P4) = 1
示例2:
L(P1) = 9, W(P1) = 10
L(P2) = 1, W(P2) = 1
L(P3) = 5, W(P3) = 10
L(P4) = 5, W(P4) = 10
这两个参数对目标函数的影响无法在本地确定，因此经过任何修改的 Floyd–Warshall 算法都将不起作用。
由于您只考虑循环，因此您可能需要考虑一种强力算法来验证图中每个循环的平均权重。您可以在多项式时间内完成，请参阅: Finding all cycles in graph
关于algorithm - 寻找有向图中最小平均权重的循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19441686/