所以我陷入了一个问题,当每条边有 2 个权重并且第二个权重(右侧)只能用作边权重时,我无法弄清楚如何应用 dijkstras 算法来找到 A 和 C 之间的最短距离如果我们访问任何带下划线的节点,否则我们只使用第一个权重作为边权重。
我尝试使用普通的 dijkstras 解决它但是卡住了,因为它没有向前移动以循环回到 A 并将最短的 pah 从 A 返回到 C
将第一个权重视为您的 SUV 到达边缘所花费的时间,将第二个权重视为另一辆小型汽车到达节点所花费的时间。你只能在带下划线的节点上换车,一旦你坐在一辆小车上,你可以用第二次重量作为所用时间,但如果第二次比第一次大,你也可以使用小车上的时间。
从a到c的最短路径应该是[A,D,E,A,D,C] 270分钟
将图𝐺复制为图𝐺',并进行以下更改:
执行 Dijkstra 算法找到从 𝐴 到 𝐶' 的最短路径。将找到的路径映射到原始图中的路径,从中删除 (𝑢,𝑢') 步骤和“重音”。