图中的最短路径,当必须跳过每一秒的边缘时

Question

我一直在为编程竞赛做准备,我偶然发现了这个问题,我必须在加权和无向图中找到从源到目的地的最短路径,但我必须跳过每一秒的边缘(所以它的重量并不重要) .图中的权重是正整数.

原始声明:

克拉拉和杰克正在旅途中.他们轮流驾驶,每个城市之后都会改变汽车司机.找到从源头到目的地的最短路径,克拉拉开出最少的里程.写第一个应该是汽车司机的人.

解决这个问题的最佳方法是什么？是否有任何修改任何算法来轻松解决？

编辑:跳跃的边缘的权重等于0,如果可以跳过边缘,我必须检查两个选项.

Answer 1

如果我理解正确你想要在加权图中找到最短路径,其中额外的复杂性是路径的权重是奇数边(1,3,......)或偶数边(2 )的权重之和,4,...)沿着这条路.

您可以先创建一个新图表来执行此操作:

1. 每个顶点v的原始图,在新的图形创建两个顶点,一个将被调用even v,另一个odd v
2. 如果(u, v)是w原始图形中的权重边缘,请将以下边缘添加到新图形:(even u, odd v)重量w和(odd u, even v)重量0

然后做两个通常的Dijkstra找到到达odd destination和even destination来自的最短路径even source.如果克拉拉第一次开车,那么重量最轻的那条路线是最短路径.

做同样的程序,从odd source找到最短路径开始,如果克拉拉开车第二.

证明

我们想要在新图中具有的不变量是:

• even v 是通过最后一个边是偶数的路径到达的顶点
• odd v 是通过最后一个边是奇数的路径到达的顶点

因为我们只从边缘添加even到odd从odd到even这个不变的是整个新图真.我们使用0偶数边的权重来容纳路径的特殊加权函数.

所述source原始图形映射到even source在新的图形已它是由含有路径到达0边缘如果克拉拉驱动第一.当克拉拉驾驶第二,source映射到odd source.

destination在原始图形中可以映射到任一路径even destination或odd destination取决于路径上的边缘数量.通过采用最短加权路径,我们确保使用原始图中的特殊加权函数找到最短路径.