网络流

对于社交网络来说，这是更好的选择，但是它也可以包含同义词链.我想到的算法是 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.