algorithm - 如何获得有向图中每两个顶点的最大几何平均路径

Question

我将通过这个例子来说明我的问题。 如上图有向图对于A到C的路径表示(A,C)，存在三种路径:
A->B->C
A->C
A->B->D->C
它们的几何平均数是:
Math.pow(0.1*0.4,1/2)=0.2
Math.pow(0.4,1)=0.4
Math.pow(0.1*0.1*0.8,1/3)=0.2
显然，最大值为0.4，也就是说最大几何平均路径为A->C

然后我想要实现的是为每两个顶点获取最大几何平均路径。我目前的方法是使用DFS获取每两个顶点的所有路径，然后计算每条路径的几何平均值并获得最大值。
但是顶点数超过300个，图形非常复杂。那么它会牺牲太多太多的时间才能得到结果。
所以我想知道是否存在更优雅的算法可以更快地解决这个问题。我知道用于多源最短路径的 floyd 算法。但似乎我不能用这个算法来解决我的问题。如果有任何建议、链接或任何相关内容，我将不胜感激。

Answer 1

由于几何平均数等于(L_1 L_2 ... L_n)^(1/n)，其自然对数等于1/n * (log(L_1) + log(L_2) + ... + log(L_n)。由于 log 函数是严格单调的，这意味着具有最大几何平均边长条件的路径与具有最大算术平均 log(edge length) 的路径相同。因此，第一个简化是替换每个边长及其对数并将您的条件重新定义为搜索最大算术平均边长。自然地，应删除任何等于 0 的边长，因为包含此边的路径永远不会具有最大值(除非每条边的长度均为 0) . 这种重新措辞不一定有多大帮助，但它消除了一些人为的(即乍一看很明显的)困难。

接下来，必须处理您想要最大平均边长而不是总边长这一事实。在所有长度为n的路径中，算术平均边长最大的路径为总长度最大的路径。所以，选择平均边长最大的路径等同于选择L_n/n最大的路径，其中L_n是最大n条边路径的长度。我没有仔细考虑细节，但在我看来，应该可以直接计算 L_n(即，找到具有最大边长的路径所需的难度，这仍然是 NP 难), 也许用动态规划。