图中的最短路径，在必须跳过每两条边之间的情况下

Question

图中的最短路径，在必须跳过每两条边之间的情况下

algorithmgraphshortest-path

6

我一直在为编程竞赛做准备，遇到了这个问题：在加权的无向图中找到从源点到目标点的最短路径，但我必须跳过每第二条边（因此它的权重不重要）。图中的权重为正整数。

原始陈述如下：

克拉拉和杰克正在旅行。他们轮流驾驶汽车，每开完一个城市后更换司机。找到从起点到终点的最短路径，使克拉拉开车的里程数最少。写出应该先让谁开车。

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

编辑：跳跃边的权重等于0，如果可以跳过边，则必须检查两个选项。

- SimpleName

1

“跳过每个第二条边”是什么意思？是在（尚未知的）最短路径上跳过每个第二条边吗？还是在松弛步骤中跳过每个第二条边。但这将取决于您放松边缘的顺序和使用的算法。如果采用任何Dijkstra变体（Dijkstra，A *，ALT，Arc Flags等），然后跳过每个第二条边，那有什么问题呢？目前，该要求对我来说没有太多意义，如果使用了具有极大预计算并改变松弛顺序的算法，例如Contraction Hierarchies，会怎样呢？您需要详细说明。 - Zabuzard

我明白了，这很显然。我的意思是，如果我们步行到达当前顶点（到达它并不是免费的），现在我们可以跳过下一个边缘到相邻的顶点（所以这是免费的）。你是对的，每隔第二个边缘的松弛应该正常工作，我在纸上解决这个问题时犯了错误，这创造了不存在的问题，谢谢;) - SimpleName

我想要检查两个选项，一个是蓝色的时候，另一个是后来变成红色的时候。 - SimpleName

请提供原始声明的链接。如此描述并不真实合理。这也将有助于使用在线评测机验证答案（如果有）。 - fjardon

@Okabe 但是这样就需要遵循图中的每条路径。而且一旦你确定了目的地，就不能停止算法，因为你不知道是否有另一条路径会将当前最短路径候选的高成本边权重设置为0。这意味着你必须解决整个图（或至少到达目的地的每个节点）。 - Zabuzard

显示剩余3条评论

3个回答

4

对于每一对相邻的边，按照图片上的方式插入一对有向边，这里假设每一对中的第一条边不计算在内。

现在你需要在有向图中找到最短路径，但不是到达目标顶点，而是找到到达目标顶点以及距离目标顶点为1的所有顶点的最短路径，然后你可以轻松推导出最短路径长度。

- Yola

1

这个解决方案如何解决 OP 想要将“每第二条边”的边权值操纵为 0 的问题？另外，它如何避免像这里所示的问题，其中松弛的顺序明显改变了哪些边被视为“第二条边”？目前描述仍不清楚，问题是不可靠的。 - Zabuzard

@Zabura 我相信 OP 是在谈论任何路径中的第二个边，因此对于每条路径，这样的边的集合是不同的。同一条边可以根据您选择的路径而计算或不计算。 - Yola

是的，我必须检查该问题中所有可能的路径。但是如果存在一个循环a-b，b-c，c-d，d-a，那么我们通过2条可能的路径计算从a到c的成本，我们是否会选择较少的成本呢？ - SimpleName

1

@Zabuza 我假设所有的权重都是正数。我们讨论的是路径上每隔一个边，而不是图上的每个边。 - Yola

@Okabe 是的，你需要在新图上运行任何算法。 - Yola

显示剩余6条评论

2

修改Bellman-Ford算法，为每个顶点记录两个距离：通过偶数和奇数条边可达的最小距离。在更新步骤（维基百科文章中的第2步），根据路径长度适当地使用零或实际权重更新距离。

https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

- Dave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fjardon · Accepted Answer

如果我理解正确，您想在加权图中找到最短路径，并且路径的权重是路径上奇数边（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算法，分别从even源到达odd目标和even目标，找到最短路径。如果Clara是首先驾驶，则具有最小权重的路径是最短路径。

从odd源开始执行相同的过程，以找到Clara第二次驾驶的最短路径。

我们想要在新图中拥有的不变量是： - even v是通过其最后一条边编号为偶数的路径到达的顶点 - odd v是通过其最后一条边编号为奇数的路径到达的顶点

由于我们只从even到odd和从odd到even添加边，因此该不变量对于整个新图都成立。我们将偶数编号的边的权重设置为0，以适应路径的特殊加权函数。

原始图中的源映射到新图中的even源，如果Clara首先驾驶，则通过包含0条边的路径到达。当Clara第二次驾驶时，源映射到odd源。

原始图中的目标可能映射到even目标或odd目标，具体取决于路径上的边数。通过找到任一目标的最短加权路径，我们确保使用原始图中的特殊加权函数找到最短路径。