查找多个短路径的算法 [英] Algorithm to find multiple short paths

问题描述

寻求一种可以产生N条短路径的算法.

Seeking an algorithm that will yield N short paths.

有人在使用有向图上找到多个短路径的算法方面有经验吗?我的应用程序用于语言(查找同义词链)，但是从逻辑上讲，它可以用于地理或社交网络.我想要明显不同的路径，而不仅仅是沿途交换一些节点.我真的很想知道是否存在避免枢纽"的方法，即大型机场或超级连接器；或在语言中，具有大量含义的单词.

Does anyone have experience with an algorithm to find multiple short paths in a directed graph? My application is for language (finding synonym chains) but logically, this could be for geography, or social networks instead. I want significantly different paths, not just swapping a few nodes along the way. I would really like also if there's a way to avoid "hubs", i.e. huge airports or super-connectors; or in language, words that have a ton of meanings.

(对于我的应用程序，我已经用Dijkstra和A-star解决了这个问题，但是除了在改变权重之后，我还没有一种好方法来获得多条路径我有第一个路径.)

(For my application, I've solved this with Dijkstra's and A-star, but I don't have a good way yet to get multiple paths, other than changing weights after I get the first path.)

例如(如果是社交网络)，我如何找到连接ME和YOU的多条路径，沿途中​​大多数人是不同的.可能会有4-7个分离点.对于语言和社交网络，分离度通常约为6度.即很少需要20个以上的节点.

For example (if a social network), how do I find multiple paths that connect ME and YOU, with mostly different people along the way. Chances are with 4-7 points of separation, that's possible. For both language, and social networks, it's often around 6 degrees of separation. i.e. it rarely takes 20+ nodes.

我看过 Dijkstra的算法可以找到所有最短的算法可能的路径，最短路径算法的变体， BFS与Dijkstra在寻找最短路径时的算法?，找到具有以下内容的最短路径A *算法-但我寻求的都不是.

I've seen Dijkstra's algorithm to find all the shortest paths possible, a variation of shortest path algorithm, What is difference between BFS and Dijkstra's algorithms when looking for shortest path?, Find several shortest paths with A* algorithm -- but none are what I seek.

当然有人知道了，但是我不知道要搜索什么.

Surely someone has figured this out, but I don't know what to search for.

推荐答案

网络流

对于社交网络来说，这是更好的选择，但是它也可以包含同义词链.我想到的算法是 Dinic的，因为它选择了扩展路径作为最短可用路径.这将使我们能够修改算法以适合您的情况.另外请注意，我们将使用整数网络流.

Network flows

This one is better for the social networks case, however it could be bent to include the synonym chains as well. The algorithm I have in mind is the Dinic's since it's augmenting paths are selected to be the shortest available paths. This will allow us to modify the algorithm to suit your case. Also note that we will be working with integer network flows.

图形构造:

• 来源，下沉
• 对于每个人p，节点p _s ，p _e 和有向边(p _s ，p _e )，容量为1. ¹
• 对于原始图形中的每个边(u，v)，均包含一连串边(u _e ，x ₁ )，(x ₁ ，x ₂ )，...(x _k ，v _s )，这样链节的数量等于链节的权重.(u，v). ² 这是为了利用Dinic发现电流的最短改进，从而惩罚了较长的链，以免过早使用
• 对于要开始的人 a ，将(x _s ，x _e )的容量更改为路径数您希望找到的. ³
• 从源到x _s
投放容量不受限制的边
• 将目标对象与水槽合并.(或添加适当的边缘)

• source, sink
• for every person p, nodes p_s, p_e and a directed edge (p_s, p_e) with the capacity of one.¹
• for every edge (u,v) in your original graph a chain of edges (u_e, x₁), (x₁, x₂), ... (x_k, v_s) so that the number of the chain links equals the weight of the (u, v).² This is to make use of the fact that Dinic finds the shortest improvement to the current flow so this penalizes the longer chains from being used too early.
• For the person a you want to start with, change the capacity of (x_s, x_e) to the number of paths you wish to find.³
• Ad an edge with unlimited capacity from the source to x_s
• Merge your target person with the sink. (Or add the appropriate edges)

运行Dinic的算法.结果流将包含最大数量的分离路径.如果您足够快地终止算法，则这些时间可能很短，因为这是算法开始的时间.但是，由于我们在图中构建的网络流尝试使不连续路径的数量最大化，因此，如果它增加了计数，它将开始偏爱较长的路径.这就是为什么您可能要限制第一个节点边缘的容量的原因.

Run the Dinic's algorithm. The resulting flow will consist of the maximal number of disjunct paths. If you terminate the algorithm soon enough, these will likely be quite short since that is what the algorithm starts with. However since the network flow in the graph we constructed attempts to maximize the number of disjunct paths, it will start to prefer the longer ones if it improves the count. That is why you might want to limit the capacity of the first node's edge.

¹ 在这种情况下，较大的容量将不起作用，因为这只会均匀增加通过最短路径的流量.但是，如果希望至少允许几个集线器或者分支稍后开始，可以尝试调整一些边缘.
² 请注意，如果您有未加权的图形，则边缘(u _e ，v _s )就足够了.
³ 或无穷大，如果您想找到所有的.这可能是因为它们的成本不再足够短.

¹Bigger capacities won't work for this case because it would just increase the flow through the shortest path uniformly. However you can try to tweak some of the edges if you wish to allow at least few hubs or if your branching starts later.
²Note that if you have unweighted graph, then the edge (u_e, v_s) will be enough.
³Or infinity if you wish to find all of them. This would likely come with the cost of them no longer being reasonably short.

这篇关于查找多个短路径的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！