寻求一种能够产生 N 条短路径的算法。
有没有人有算法的经验来寻找多条短路径在有向图中？我的应用程序用于语言（查找同义词链），但从逻辑上讲，这可能用于地理或社交网络。我想要明显不同的路径，而不仅仅是沿途交换几个节点。我真的很想知道是否有办法避免“枢纽”，即大型机场或超级连接器；或者在语言中，有很多含义的单词。
（对于我的应用程序，我已经用 Dijkstra 和 A-star 解决了这个问题，但我还没有一个好的方法来获得多条路径，除了在获得第一条路径后改变权重。）
例如（如果是社交网络），我如何找到连接我和你的多条路径，沿途大多是不同的人。可能有 4-7 个分离点，这是可能的。对于语言和社交网络来说，通常有 6 度左右的分离度。也就是说，很少需要 20 个以上的节点。
我见过Dijkstra 算法寻找所有可能的最短路径 https://stackoverflow.com/questions/2819347/dijkstras-algorithm-to-find-all-the-shortest-paths-possible, 最短路径算法的一种变体 https://stackoverflow.com/questions/22026691/a-variation-of-shortest-path-algorithm, 在寻找最短路径时，BFS 和 Dijkstra 算法有什么区别？ https://stackoverflow.com/questions/25449781/what-is-difference-between-bfs-and-dijkstras-algorithms-when-looking-for-shorte?rq=1, 用A*算法找到几条最短路径 https://stackoverflow.com/questions/28739853/find-several-shortest-paths-with-a-algorithm——但没有一个是我所寻求的。
当然有人已经弄清楚了这一点，但我不知道要搜索什么。
网络流量
这对于社交网络的情况来说更好，但是它也可以包含同义词链。
我想到的算法是Dinic's https://en.wikipedia.org/wiki/Dinic%27s_algorithm因为它的增广路径被选择为shortest可用路径。这将使我们能够修改算法以适合您的情况。另请注意，我们将与integer网络流量。
图构建：
- 源、汇
- for every person p, nodes ps, pe and a directed edge
(ps, pe) with the capacity of one.1
- for every edge (u,v) in your original graph a chain of edges (ue, x1), (x1, x2), ... (xk, vs) so that the number of the chain links equals the weight of the (u, v).2 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 (xs, xe) to the number of paths you wish to find.3
- Ad an edge with unlimited capacity from the source to xs
- 将目标人物与水槽合并。 （或添加适当的边）
运行 Dinic 算法。生成的流将包含最大数量的分离路径。如果您足够快地终止算法，这些可能会很短，因为这就是算法的开始。然而，由于我们构建的图中的网络流尝试最大化分离路径的数量，因此如果它提高了计数，它将开始更喜欢较长的路径。这就是为什么您可能想要限制第一个节点边缘的容量。
1Bigger 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.
2Note that if you have unweighted graph, then the edge (ue, vs) will be enough.
3Or infinity if you wish to find all of them. This would likely come with the cost of them no longer being reasonably short.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
