寻找多条短路径的算法
Algorithm to find multiple short paths
寻求一种算法，该算法将产生 N 条短路径。
有没有人有使用算法在有向图中找到多条短路径的经验？我的应用程序是针对语言的（查找同义词链），但从逻辑上讲，这可能是针对地理或社交网络的。我想要截然不同的路径，而不仅仅是沿途交换几个节点。如果有一种方法可以避免“枢纽”，即大型机场或超级连接器，我也真的很想；或者在语言中，有很多含义的单词。
（对于我的应用程序，我已经用 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 -- 但 none 是我想要的。
肯定有人已经弄清楚了，但我不知道要搜索什么。
网络流量
这个更适合社交网络案例，但它也可以包含同义词链。
我想到的算法是 Dinic's 因为它的增广路径被选为 最短 可用路径。这将使我们能够修改算法以适合您的情况。另请注意，我们将使用 整数 网络流。
图构造：
- 源、汇
- for every person p, nodes ps, pe and a directed edge
(ps, pe)容量为1.1
- 原始图中的每条边 (u,v) 都是边链 (ue, x1), ( x1, x2), ... (xk, v s) 使得链节的数量等于 (u, v) 的权重。2 这是利用 Dinic 发现 最短 对当前流程的改进，因此这会惩罚过早使用较长的链。
- 对于你想入手的人a，改变容量(xs, xe ) 到您要查找的路径数。3
- 添加一条从源到 xs
无限容量的边
- 将目标人物与水槽合并。 （或添加适当的边）
运行 狄尼克算法。生成的流将包含最大数量的分离路径。如果你足够快地终止算法，这些可能会很短，因为这是算法的开始。然而，由于我们构建的图中的网络流试图最大化分离路径的数量，因此如果它提高计数，它将开始更喜欢较长的路径。这就是为什么您可能想要限制第一个节点边缘的容量。
1更大的容量不适用于这种情况，因为它只会均匀地增加通过最短路径的流量。但是，如果您希望至少允许几个集线器或者如果您的分支稍后开始，您可以尝试调整 一些 边缘。
2注意，如果你有未加权的图，那么边(ue, vs)将够了。
3或者如果你想找到所有的无穷大。这可能会伴随着它们的成本不再相当低。
这是@Shamis 已经提供的答案的变体。它允许重复使用节点，因此如果出现瓶颈，您仍然可以找到 n 解决方案。
比最大流量更一般的是minimum cost flow。所以试试这个。
根据你的图表，给出每条边的容量 1 和成本 1。现在为容量 1 和成本 4 的每个第一个边添加第二个边。 （我使用 4 作为启发式算法，使其尽可能避开该边。）添加容量为 1 且成本为 16 的第三条边。以此类推，直到成本 4^n.
的边缘
在this book中，您会发现以下关于最小成本流的不明显结果：
由于基本可行解都是整数值，所以当有最优解时，就会有一个是整数值。这使得即使在需要整数值解决方案时，也可以使用线性规划算法来解决最小成本流问题。我们将在以下小节中讨论一些示例。
我们现在寻找容量的最小成本流 n。如果有 n 个独立的解决方案，您就会找到它们。如果他们必须重用节点，您会发现很难避免重用节点的解决方案。如果需要，他们会走得更远。
如果您将序列 1, 4, 16, ... 更改为其他内容，您将在接受更长的解决方案和避免重复的解决方案之间做出不同的权衡。
我没有提供关于这有多有效的估计。只是它是可行的。
寻求一种算法，该算法将产生 N 条短路径。
有没有人有使用算法在有向图中找到多条短路径的经验？我的应用程序是针对语言的（查找同义词链），但从逻辑上讲，这可能是针对地理或社交网络的。我想要截然不同的路径，而不仅仅是沿途交换几个节点。如果有一种方法可以避免“枢纽”，即大型机场或超级连接器，我也真的很想；或者在语言中，有很多含义的单词。
（对于我的应用程序，我已经用 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 -- 但 none 是我想要的。
肯定有人已经弄清楚了，但我不知道要搜索什么。
网络流量
这个更适合社交网络案例，但它也可以包含同义词链。 我想到的算法是 Dinic's 因为它的增广路径被选为 最短 可用路径。这将使我们能够修改算法以适合您的情况。另请注意，我们将使用 整数 网络流。
图构造：
- 源、汇
- for every person p, nodes ps, pe and a directed edge (ps, pe)容量为1.1
- 原始图中的每条边 (u,v) 都是边链 (ue, x1), ( x1, x2), ... (xk, v s) 使得链节的数量等于 (u, v) 的权重。2 这是利用 Dinic 发现 最短 对当前流程的改进，因此这会惩罚过早使用较长的链。
- 对于你想入手的人a，改变容量(xs, xe ) 到您要查找的路径数。3
- 添加一条从源到 xs 无限容量的边
- 将目标人物与水槽合并。 （或添加适当的边）
运行 狄尼克算法。生成的流将包含最大数量的分离路径。如果你足够快地终止算法，这些可能会很短，因为这是算法的开始。然而，由于我们构建的图中的网络流试图最大化分离路径的数量，因此如果它提高计数，它将开始更喜欢较长的路径。这就是为什么您可能想要限制第一个节点边缘的容量。
1更大的容量不适用于这种情况，因为它只会均匀地增加通过最短路径的流量。但是，如果您希望至少允许几个集线器或者如果您的分支稍后开始，您可以尝试调整 一些 边缘。
2注意，如果你有未加权的图，那么边(ue, vs)将够了。
3或者如果你想找到所有的无穷大。这可能会伴随着它们的成本不再相当低。
这是@Shamis 已经提供的答案的变体。它允许重复使用节点，因此如果出现瓶颈，您仍然可以找到 n 解决方案。
比最大流量更一般的是minimum cost flow。所以试试这个。
根据你的图表，给出每条边的容量 1 和成本 1。现在为容量 1 和成本 4 的每个第一个边添加第二个边。 （我使用 4 作为启发式算法，使其尽可能避开该边。）添加容量为 1 且成本为 16 的第三条边。以此类推，直到成本 4^n.
在this book中，您会发现以下关于最小成本流的不明显结果：
由于基本可行解都是整数值，所以当有最优解时，就会有一个是整数值。这使得即使在需要整数值解决方案时，也可以使用线性规划算法来解决最小成本流问题。我们将在以下小节中讨论一些示例。
我们现在寻找容量的最小成本流 n。如果有 n 个独立的解决方案，您就会找到它们。如果他们必须重用节点，您会发现很难避免重用节点的解决方案。如果需要，他们会走得更远。
如果您将序列 1, 4, 16, ... 更改为其他内容，您将在接受更长的解决方案和避免重复的解决方案之间做出不同的权衡。
我没有提供关于这有多有效的估计。只是它是可行的。