如何在具有 2 个给定边权重的图上实现 Dijkstra's，并有条件使用另一个？

Question

我遇到了一个问题，当每条边有 2 个权重并且第二个权重（右侧）只能用作边权重时，我无法弄清楚如何应用 Dijkstra 算法找到 A 和 C 之间的最短距离我们访问任何带下划线的节点，否则我们只使用第一个权重作为边权重。

我尝试使用普通的 Dijkstra 解决它但卡住了，因为它没有向前移动以循环回到 A 并返回从 A 到 C 的最短路径。

将第一个权重视为您的 SUV 到达边缘所花费的时间，将第二个权重视为另一辆小型汽车到达节点所花费的时间。只能在划线节点换车，坐小车可以取第二次的重量作为时间，如果第二次比第一次大也可以用小车的一次。

从a到c的最短路径应该是[A,D,E,A,D,C] 270分钟

Answer 1

将图𝐺复制为图𝐺'，并进行以下更改：

• 在𝐺中，移除第二条边，使其只有第一条边
• 在𝐺'中，移除第一条边，使其只有第二条边
• 对于𝐺中每个带下划线的顶点𝑢，从𝑢添加一条权重为0的有向边到它在𝐺'中的复制顶点𝑢'。还添加从𝐶到𝐶'的零权重边。

执行 Dijkstra 算法找到从 𝐴 到 𝐶' 的最短路径。将找到的路径映射到原始图中的路径，从中删除 (𝑢,𝑢') 步骤和“重音”。

Answer 2

• 仅使用第一个权重在图上运行 Dijkstra。路径 1
• 创建第二个图表
• 在第二张图中添加带下划线的顶点
• 第二张图使用第二个权重在带下划线的顶点之间添加边
• 使用 Dijkstra 找到第二个图中未连接的带下划线的顶点之间的最便宜路径，使用第二个权重。添加权重设置为路径权重的边。
• 在第二张图中运行 Dijkstra。路径 2
• Path 1 和 Path 2 的输出最便宜