找到多个短路径的算法

Question

寻求一种将产生 N 条短路径的算法。
有没有人有使用算法找到 的经验？多条短路径 在有向图中？我的应用程序是针对语言(查找同义词链)，但从逻辑上讲，这可能是针对地理或社交网络的。我想要明显不同的路径，而不仅仅是沿途交换几个节点。如果有办法避免“枢纽”，即巨大的机场或 super 连接器，我也真的很想；或在语言中，具有大量含义的词。
(对于我的应用程序，我已经用 Dijkstra 和 A-star 解决了这个问题，但我还没有一个好的方法来获得 多条路径 ，除了在我获得第一条路径后改变权重。)
例如(如果是社交网络)，我如何找到连接我和你的多条路径，一路上大多是不同的人。有可能有 4-7 个分离点，这是可能的。对于语言和社交网络，通常有 6 度左右的分离度。即它很少需要 20 多个节点。
我见过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 ——但没有一个是我所寻求的。
肯定有人发现了这一点，但我不知道要搜索什么。

Answer 1

网络流量
这个更适合社交网络案例，但也可能倾向于包含同义词链。
我想到的算法是 Dinic's因为它的增广路径被选为 最短可用路径。这将允许我们修改算法以适合您的情况。另请注意，我们将使用 整数 网络流量。
图构建:

源、汇

对于每个人 p、节点 ps、pe 和有向边
(ps, pe) 容量为 one.1

对于原始图中的每条边 (u,v)，一条边链 (ue, x1), (x1, x2), ... (xk, vs) 使得链节的数量等于 ( u, v).2 这是为了利用 Dinic 找到 的事实。最短改进了当前的流程，因此这会惩罚过早使用较长的链。

为人 您想开始时，将 (xs, xe) 的容量更改为您希望找到的路径数。3

将具有无限容量的边缘从源添加到 xs

将目标人员与接收器合并。 (或添加适当的边)

运行 Dinic 算法。结果流将由最大数量的分离路径组成。如果您足够快地终止算法，这些可能会很短，因为这是算法的开始。然而，由于我们构建的图中的网络流试图最大化分离路径的数量，如果它提高计数，它将开始更喜欢较长的路径。这就是您可能想要限制第一个节点边缘容量的原因。

1更大的容量不适用于这种情况，因为它只会均匀地增加通过最短路径的流量。但是你可以尝试调整 一些 如果您希望允许至少几个集线器或者如果您的分支稍后开始。
2注意，如果你有未加权的图，那么边(ue，vs)就足够了。
3或者无穷大，如果你想找到所有的。这可能会导致它们的成本不再合理短。