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

Consider the following graph:

请考虑以下图表:

nodes 1 to 6 are connected with a transition edge that have a direction and a volume property (red numbers). I'm looking for the right algorithm to find paths with a high volume. In the above example the output should be:

节点1到6与具有方向和体积属性(红色数字)的过渡边缘连接。我正在寻找合适的算法来查找高音量的路径。在上面的例子中,输出应该是:

1. Path: [4,5,6] with a minimal volume of 17

路径:[4,5,6],最小音量为17

2. Path: [1,2,3] with a minimal volume of 15

路径:[1,2,3],最小音量为15

I've looked at Floyd–Warshall algorithm but I'm not sure it's the right approach.

我看过Floyd-Warshall算法,但我不确定这是正确的方法。

Any resources, comments or ideas would be appreciated.

任何资源,评论或想法将不胜感激。

1 个解决方案

#1

Finding a beaten graph:

找到一个被打的图:

In the comments, you clarify that you are looking for "beaten" paths. I am assume this means that you are trying to contrast the paths with the average; for instance, looking for paths which can support weight at least e*w, where 0<e and w is the average edge weight. (You could have any number of contrast functions here, but the function you choose does not affect the algorithm.)

在评论中,您澄清了您正在寻找“挨打”的路径。我认为这意味着你试图将路径与平均值进行对比;例如,寻找能够支持至少e * w的权重的路径,其中0 且w是平均边缘权重。>

Then the algorithm to find all paths that meet this condition is incredibly simple and only takes O(m) time:

然后找到满足这个条件的所有路径的算法非常简单,只花费O(m)时间:

1. Loop over all edges to find the average weight. (Takes O(m) time.)

环绕所有边缘以找到平均重量。 (花费O(m)时间。)

2. Calculate the threshold based on the average. (Takes O(1) time.)

根据平均值计算阈值。 (花费O(1)时间。)

3. Remove all edges which do not support the threshold weight. (Takes O(m) time.)

移除所有不支持阈值重量的边缘。 (花费O(m)时间。)

4. Any path in the resulting graph will be a member of the "widest path collection."

结果图中的任何路径都将是“最宽路径集合”的成员。

Example:

Consider that e=1.5. That is, you require that a beaten path support at least 1.5x the average edge weight. Then in graph you provided, you will loop over all the edges to find their average weight, and multiply this by e:

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

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

Then you loop over all edges, removing any that have weight less than 13.8. Any remaining paths in the graph are "beaten" paths.

然后循环所有边缘,移除任何重量小于13.8的边缘。图中任何剩余的路径都是“挨打”的路径。

Enumerating all beaten paths:

列举所有被打败的路径:

If you then want to find the set of beaten paths with maximal length (that is, they are not "parts" of paths), the modified graph is must be a DAG (because a cycle can be repeated infinite times). If it is a DAG, you can find the set of all maximal paths by:

如果您想要找到具有最大长度的一组跳动路径(即,它们不是路径的“部分”),则修改后的图形必须是DAG(因为循环可以重复无限次)。如果是DAG,您可以通过以下方式找到所有最大路径的集合:

1. In your modified graph, select the set of all source nodes (no incoming edges).

在修改后的图形中,选择所有源节点的集合(无入射边缘)。

2. From each of these source nodes, perform a DFS (allowing repeated visits to the same node).

从每个源节点执行DFS(允许重复访问同一节点)。

3. Every time you get to a sink node (no outgoing edges), write down the path that you took to get here.

每次到达汇聚节点(没有传出边缘)时,请记下您到达此处的路径。

This will take up to O(IncompleteGamma[n,1]) time (super exponential), depending on your graph. That is, it is not very feasible.

这将占用O(不完全伽玛[n,1])时间(超指数),具体取决于您的图表。也就是说,它不太可行。

Finding the widest paths:

找到最宽的路径:

An actually much simpler task is to find the widest paths between every pair of nodes. To do this:

实际上更简单的任务是找到每对节点之间最宽的路径。去做这个:

1. Start from the modified graph.

从修改后的图表开始。

2. Run Floyd-Warshall's, using pathWeight(i,j,k+1) = max[pathWeight(i,j,k), min[pathWeight(i,k+1,k), pathWeight(k+1,j,k)]] (that is, instead of adding the weights of two paths, you take the minimum volume they can support).

运行Floyd-Warshall,使用pathWeight(i,j,k + 1)= max [pathWeight(i,j,k),min [pathWeight(i,k + 1,k),pathWeight(k + 1,j,k) )]](也就是说,不是添加两条路径的权重,而是采用它们可以支持的最小音量)。