graph-theory - 带油箱的最短路径

Question

这是一个家庭作业问题，我很乐意提供一些指导。

设 G=(V,E) 是一个无向图，其中每个顶点代表一个城市，边的权重代表旅行距离。有些城市有加油站。汽车从顶点 s 开始，油箱足以行驶长度 L。我需要找到 s 和 t 之间的最短路径，以便汽车不会耗尽汽油。

我的主要想法是使用 Floyd-Warshall 算法进行一些更改。当我们计算 shortestPath(i,j,0) 时，如果 i 有加油站并且 L-w(i,j) > 0 则分配 w(i,j) ，否则分配无穷大。但是，对于接下来的步骤，我不知道如何将当前的燃料状态添加到计算中。

谢谢。

Answer 1

用顶点制作新的加权图:s , t和有加油站的城市 (C)。

边缘:

s-c , 与 c来自 C , 如果 s 之间有最短路径和 c有长度<= L ,

c1-c2 , 与 c1 , c2来自 C , 长度 c1-c2 <= L ,

c-t , 与 c来自 C , 长度 c-e <= L ,

s-t , 如果长度 s-t <= L .

并且边缘权重设置为长度 v1-v2 .

此图上的标准 Dijkstra 应返回您在原始图上寻找的最短路径的骨架。

当 Dijkstra 要求边界顶点上的边时，可以“迭代地”创建新图。类似的，先创建 s-c和 s-t边(和顶点)，如果有需求 c1-c2和 c-t而不是将这些顶点和边添加到图中。