这是一个家庭作业问题，我很乐意提供一些指导。
让 G=(V,E) 是一个无向图，其中每个顶点代表一个城市，边具有代表旅行距离的权重。一些城市有加油站。一辆汽车从顶点 s 开始，油箱足以行驶长度 L。我需要找到 s 和 t 之间的最短路径，这样汽车就不会耗尽汽油。
我的主要想法是使用 Floyd-Warshall 算法并进行一些更改。当我们计算 shortestPath(i,j,0) 时，如果 i 有加油站并且 Lw(i,j) > 0 ，则分配 w(i,j) ，否则分配无穷大。但是，对于接下来的步骤，我不知道如何将当前的燃料状态添加到计算中。
谢谢。
用顶点： 和城市（ ）与加油站制作新的s加权t图C。
边缘：
s-c, 与cfrom C, 如果在 和 之间有最短路径s,c有长度<= L,c1-c2, , c1,c2从C, 长度c1-c2 <= L,c-t,c来自C, 长度c-e <= L,s-t, 如果长度s-t <= L.并将边缘权重设置为 length v1-v2。
此图上的标准 Dijkstra 应返回您在原始图上寻找的最短路径的骨架。
当 Dijkstra 要求边界顶点上的边时，可以“迭代地”创建新图。例如，首先创建s-c边s-t（和顶点），如果需要，c1-c2然后c-t将这些顶点和边添加到图中。