graph - 忽略一项成本找到最便宜的路径

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'。

通过添加额外的副本并将每个新副本链接到最后一个副本，您可以从那里推广到任意数量的百搭边。但是，在这种情况下，您可能必须使用更少的百搭来添加目标，以解决最短路径需要的边少于百搭的情况。