I have a graph with V vertices and E edges. Each edge is a road that takes fuel F to travel. I have a gas tank of capacity K, and want to find the fewest number of refills needed to go from any vertex to any other vertex. If I choose to refuel, I can fill the tank completely.
My thought is to modify the Floyd - Warshall Algorithm to keep track of both number of refills, and amount of gas left. However, I am not sure how to proceed.
Note: This is NOT a HW question. I was reading To Fill or not to Fill: The Gas Station Problem and began to wonder.