graph - 三点之间的最短路径

Question

在图中，我需要找到两点之间的最短路径，并在途中访问一个检查点。另外，我只能访问每个顶点一次。我想它与网络流量有关，但我不知道如何实现。

Answer 1

您可以将其完全建模为一个有能力的多商品最小成本流问题。您想通过 C 从 A 到 B 而不使用两次顶点。您可以将其建模为从 A 到 C 的流（商品 1）和从 B 到 C 的流（商品 2）。为避免一个节点被使用两次，您必须在所有节点（在您的模型中）上执行以下技巧：

给定一个具有 p 个传入边和 t 个传出边的节点 X，您可以创建一个新节点 Y 并重新连接链接。p条入链将全部到达X，q条出边将全部离开Y。从X到Y只添加1条链（L）。通过将L-link的容量设置为1，每个节点将只被使用一次。

然后，您可以将其写为 (M)ILP 并解决它。如果存在，ILP 将为您提供正确的解决方案。根据您的应用程序，这可能是矫枉过正。如果您想要快速启发式，只需使用 2 个 A* 搜索并希望它们不会重叠。