找出最便宜的路径,忽略一个成本

Question

我想找到两个顶点之间最便宜的路径,我可以选择一条我可以免费使用的路径,例如:

顶点1和6之间最便宜的路径是1-3-4-5-6 - 我免费进入边缘1-3(费用30),它给我总成本21.

除了逐个检查所有路径之外还有其他方法吗？

Answer 1

一种方法是执行以下操作：

1. 复制你的图，这样你就有了带有节点 1,2 等的原始图 G。以及具有节点 1'、2' 等的副本 G'。和相应的边。
2. 对于 G 的每条边 (a,b)，制作一条从 a 到 b' 的弧（有向！），以及另一条从 b 到 a' 的弧，两者的成本均为 0。
3. 最后，使用从子图 G 的任何顶点到 G' 的任何顶点（示例中的 1 到 6'）的任何最短路径算法。

基本上，当你使用小丑时，你会从子图 G 切换到 G'。

您可以通过添加额外的副本并将每个新副本链接到最后一个副本，从那里推广到任意数量的小丑边缘。然而，在这种情况下，您可能必须使用较少的小丑来添加目标，以考虑最短路径需要的边数少于小丑的边数的情况。