假设您有一个无向加权图.您希望找到从源到目标节点的最短路径,同时从一些初始"燃料"开始.每条边的重量等于你在边缘丢失的"燃料"量.在每个节点,您可以为燃料计数添加预定量的燃料 - 该值可以为0.可以多次访问节点,但只有在您第一次到达节点时才会添加燃料.**所有节点可以提供不同数量的燃料.
这个问题可能与从A镇到B镇的火车有关.尽管两者都是通过简单的轨道直接连接,但是煤炭短缺,所以火车没有足够的燃料来进行旅行.相反,它必须进行从A镇到C镇的更短的旅程,已知有足够的燃料来覆盖返回A然后继续前往B.因此,最短的路径是从A到C的距离加上从C到A的距离加上从A到B的距离.我们假设燃料成本和距离是相等的.
我已经看到一个例子,节点总是填充"坦克"达到其最大容量,但我还没有看到一种算法在不同的节点处理不同的加油量.什么是解决此问题的有效算法？