Graph 中的最短路径，当必须跳过第二条边时
Shortest Path in Graph, when it is obligatory to jump over every second edge
我一直在为编程竞赛做准备，我偶然发现了这个问题，我必须在加权和无向图中找到从源到目的地的最短路径，但我必须跳过每一秒的边（所以它重量并不重要）。图中权重为正整数。
原文：
Clara and Jake are on trip. They are driving in turns and car driver is being changed after every city. Find shortest path from source to destination, that Clara drove least miles. Write who should be car driver first.
解决这个问题的最佳方法是什么？是否有任何算法的修改可以轻松解决？
编辑：跳跃边的权重等于 0，是否可以跳过边我必须检查两个选项。
如图所示，对于每对相邻边插入一对有向边，这里我假设不计算每对中的第一条边。
现在您需要在有向图中找到最短路径而不是到目标顶点，而是找到到目标顶点和距目标顶点距离为 1 的所有顶点的最短路径，现在您可以轻松推导出最短路径长度.
如果我理解正确的话，你想在加权图中找到最短路径，但具有额外的复杂性，即路径的权重是奇数边的权重之和 (1, 3, ...) 或沿路径的偶数边（2、4、...）。
您可以先创建一个新图表来完成此操作：
- 对于原始图中的每个顶点
v，在新图中创建两个顶点，一个称为even v，另一个称为odd v
- 如果
(u, v) 是原始图中权重 w 的边，将以下边添加到新图中：(even u, odd v)，权重 w 和 (odd u, even v) 体重 0
然后做两个通常的 Dijkstra 来找到从 even source 到达 odd destination 和 even destination 的最短路径。如果克拉拉第一个开车，那么重量最小的就是最短的路径。
执行相同的步骤，从 odd source 开始寻找最短路径，如果 Clara 驾驶第二个。
证明
我们希望新图中的不变量是：
even v 是通过最后一条边为偶数的路径到达的顶点odd v 是通过最后一条边为奇数的路径到达的顶点
因为我们只添加从 even 到 odd 和从 odd 到 even 的边，这个不变量对于整个新图都是正确的。我们对偶数边使用 0 的权重，以适应路径的特殊加权函数。
原始图中的 source 映射到新图中的 even source 如果 Clara 首先驱动，则通过包含 0 边的路径到达它。当 Clara 驾驶第二个时，source 映射到 odd source。
原始图中的 destination 可能映射到 even destination 或 odd destination，具体取决于路径上的边数。通过采用最短的加权路径，我们一定会使用原始图中的特殊加权函数找到最短路径。
修改 Bellman-Ford 以跟踪每个顶点的两个距离：通过偶数和奇数条边可实现的最小距离。在更新步骤（维基百科文章中的第 2 步）中，根据给定的路径长度，使用零或实际权重更新距离。
https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
我一直在为编程竞赛做准备，我偶然发现了这个问题，我必须在加权和无向图中找到从源到目的地的最短路径，但我必须跳过每一秒的边（所以它重量并不重要）。图中权重为正整数。
原文：
Clara and Jake are on trip. They are driving in turns and car driver is being changed after every city. Find shortest path from source to destination, that Clara drove least miles. Write who should be car driver first.
解决这个问题的最佳方法是什么？是否有任何算法的修改可以轻松解决？
编辑：跳跃边的权重等于 0，是否可以跳过边我必须检查两个选项。
如图所示，对于每对相邻边插入一对有向边，这里我假设不计算每对中的第一条边。
现在您需要在有向图中找到最短路径而不是到目标顶点，而是找到到目标顶点和距目标顶点距离为 1 的所有顶点的最短路径，现在您可以轻松推导出最短路径长度.
如果我理解正确的话，你想在加权图中找到最短路径，但具有额外的复杂性，即路径的权重是奇数边的权重之和 (1, 3, ...) 或沿路径的偶数边（2、4、...）。
您可以先创建一个新图表来完成此操作：
- 对于原始图中的每个顶点
v，在新图中创建两个顶点，一个称为even v，另一个称为odd v - 如果
(u, v)是原始图中权重w的边，将以下边添加到新图中：(even u, odd v)，权重w和(odd u, even v)体重0
然后做两个通常的 Dijkstra 来找到从 even source 到达 odd destination 和 even destination 的最短路径。如果克拉拉第一个开车，那么重量最小的就是最短的路径。
执行相同的步骤，从 odd source 开始寻找最短路径，如果 Clara 驾驶第二个。
证明
我们希望新图中的不变量是：
even v是通过最后一条边为偶数的路径到达的顶点odd v是通过最后一条边为奇数的路径到达的顶点
因为我们只添加从 even 到 odd 和从 odd 到 even 的边，这个不变量对于整个新图都是正确的。我们对偶数边使用 0 的权重，以适应路径的特殊加权函数。
原始图中的 source 映射到新图中的 even source 如果 Clara 首先驱动，则通过包含 0 边的路径到达它。当 Clara 驾驶第二个时，source 映射到 odd source。
destination 可能映射到 even destination 或 odd destination，具体取决于路径上的边数。通过采用最短的加权路径，我们一定会使用原始图中的特殊加权函数找到最短路径。
修改 Bellman-Ford 以跟踪每个顶点的两个距离：通过偶数和奇数条边可实现的最小距离。在更新步骤（维基百科文章中的第 2 步）中，根据给定的路径长度，使用零或实际权重更新距离。
https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm