下水道设计的最佳路径

Question

在给定的连接的、无向的、有权的图/网络中，有没有什么算法可以找到源和宿之间的所有路径？网络由多个源节点和一个汇聚节点组成。路径应该没有循环

Answer 1

我会使用A*算法来实现这一点，与基本路径查找有以下区别。

• 从 sink 而不是从 source 开始，因为只有一个 sink
• 每个节点都是一组位置，而不是单个位置。在每次迭代中，将所有位置的邻居添加到队列中。还为所有邻居创建分支，以便在下一组中多出一个位置。将最大位置数限制为源数作为优化。
• 跟踪您在每条路径中到达的来源
• 行进成本函数应该是所有分支路径组合的总行进距离
• 估计函数应该结合所有剩余的来源

如果正确使用A*算法，这应该会给出最优路径。

Answer 2

如果您查找所有无循环路径，则breadth-frist search应该可以完成此工作。在迭代中，对于每个当前路径，只要它到达路径或接收器上已有的点，就不要继续它。

Answer 3

它看起来很像Minimum Spanning Tree。