如何在有向加权图上找到最宽路径集合

Question

考虑下图：

节点 1 到 6 与过渡边相连，过渡边具有方向和体积 属性（红色数字）。我正在寻找合适的算法来查找大量路径。在上面的例子中，输出应该是：

1. 路径：[4,5,6]，最小音量为 17
2. 路径：[1,2,3] 最小交易量 15

我看过 Floyd–Warshall algorithm，但我不确定这是正确的方法。

如有任何资源、意见或想法，我们将不胜感激。

Answer 1

查找打败图：

在评论中，您说明您正在寻找 "beaten" 路径。我假设这意味着您正在尝试将路径与平均值进行对比；例如，寻找至少可以支持权重 e*w 的路径，其中 0

那么找到满足这个条件的所有路径的算法非常简单，只需要 O(m) 时间：

1. 遍历所有边以找到平均重量。 （需要 O(m) 时间。）
2. 根据平均值计算阈值。 （需要 O(1) 时间。）
3. 移除所有不支持阈值权重的边。 （需要 O(m) 时间。）
4. 结果图中的任何路径都将成为 "widest path collection."
的成员

示例：

考虑 e=1.5。也就是说，您需要一条人迹罕至的路径支持至少 1.5 倍的平均边权重。然后在您提供的图表中，您将遍历所有边以找到它们的平均权重，并将其乘以 e:

((20+4)+15+3+(2+20)+(1+1+17))/9 = 9.2
9.2*1.5 = 13.8

然后遍历所有边，移除所有权重小于 13.8 的边。图表中的任何剩余路径都是 "beaten" 条路径。

正在枚举所有常规路径：

如果你想找到最大长度的人迹罕至的路径集（也就是说，它们不是 "parts" 路径），修改后的图必须是 DAG（因为循环可以重复无限次）。如果是DAG，可以通过：

找到所有最大路径的集合

1. 在您修改后的图表中，select 所有源节点的集合（没有传入边）。
2. 从每个源节点执行 DFS（允许重复访问同一节点）。
3. 每次到达汇聚节点（无出边）时，记下您到达此处的路径。

这将花费 O(IncompleteGamma[n,1]) 时间（超级指数），具体取决于您的图表。也就是不太可行。

寻找最宽的路径：

实际上更简单的任务是找到每对节点之间的最宽路径。为此：

1. 从修改后的图表开始。
2. 运行Floyd-Warshall的，使用pathWeight(i,j,k+1) = max[pathWeight(i,j,k), min[pathWeight(i,k+1,k), pathWeight(k+1,j,k)]]（也就是说，不是将两个路径的权重相加，而是取它们可以支持的最小体积）。