下水道设计的最佳路径

Question

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

Answer 1

我会用一个A *算法来解决这个问题，其基本路径发现存在以下差异。

• 从信宿而不是从源开始，因为只有一个信宿
• 每个节点是一组位置，而不是一个单一的位置。在每次迭代中，将所有位置的邻居添加到队列中。还要为所有邻居创建分支，以便在下一个集合中再增加一个位置。将最大位置数限制为来源数作为优化。
• 跟踪哪些源已在每个路径到达
• 的行进成本函数应与所有分支路的总行驶距离合并
• 估计函数应结合所有剩余的源

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

Answer 2

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

Answer 3

它看起来类似于Minimum Spanning Tree。