3
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ I am not entirely sure what you are asking. Do you want to visit all vertices in one tour or do you only consider paths between two arbitrary vertices? $\endgroup$ – Dennis Kraft Oct 14 '15 at 7:29
  • 1
    $\begingroup$ Also, I am assuming that you can only refuel the tank at vertices but not along edges? $\endgroup$ – Dennis Kraft Oct 14 '15 at 9:00
  • $\begingroup$ @DennisKraft I think the question states this sufficiently clearly: find the pairwise distance matrix where distance is measured as amount of times refuelled. The part about refuelling at edges or nodes, admittedly, is ambiguous. $\endgroup$ – Lieuwe Vinkhuijzen Oct 14 '15 at 23:09
  • 1
    $\begingroup$ @LieuweVinkhuijzen Well, the question does not really state that. We can just assume it since the OP suggests to use the Floyd Warshall algorithm. $\endgroup$ – Dennis Kraft Oct 15 '15 at 8:14
1
$\begingroup$

This problem cannot be solved using a (modified) Floyd-Warshall Algorithm. The underlying assumption in F.-W. is that all paths arriving at a given node can be extended along the same path to the destination. Therefore choosing the shortest path that arrives at a node is also optimal for all paths that pass through the node. By adding the fuel constraint, this assumption is broken.

More generally, problems of this form are called the Resource-Constrained Shortest Path Problems and are, in general, $\mathcal{NP}$-hard. A generic solution to this problem is to enumerate all feasible paths that lead to any node in the graph, which obviously leads to exponential time complexity. In practice, "dominance" rules are applied to prune partial paths that are clearly inferior to other partial paths; in your case such a dominance rule could be to throw away all paths arriving at a node with more refills and less fuel than another path arriving on the same node.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Although I agree that the Floyd-Warshall algorithm is not useful here, I don't think the task at hand is NP-hard. Using Dijkstra's algorithm to compute the minimal number of refills for any ordered pair of vertices should work fine. Just use the number of refills and the remaining fuel in this lexicographic order as distance measure. $\endgroup$ – Dennis Kraft Oct 15 '15 at 16:01
  • $\begingroup$ @DennisKraft: I think you are implicitly assuming that refills are possible on every node. In this case, I agree that using lexicographic order as distance will work correctly. Also, using Floyd-Warshall would be perfectly possible in this scenario. Anyway, I had implicitly assumed that only certain nodes act as gas stations and in this case your approach is not correct, as it will throw paths with more refills but more fuel left which might be necessary to reach a certain destination. $\endgroup$ – matz Oct 16 '15 at 9:44
  • $\begingroup$ Even if refills are possible at every node, I don't think the Floyd-Warshall algorithm is straight forward to use. If it is, I would be interested in seeing how this can be done. $\endgroup$ – Dennis Kraft Oct 16 '15 at 9:54
  • $\begingroup$ @DennisKraft: Using Floyd-Warshall with a lexicographic order should not be more difficult than using Dijkstra with a lexicographic order, or where do you expect difficulties? As a side note: I've just noticed that an instance where refilling is only possible on certain nodes, can easily be preprocessed into an instance where refilling is possible on every internal node. I'm glad I wrote that the RCSPP problem is NP-hard only in general :-) $\endgroup$ – matz Oct 16 '15 at 10:16
  • $\begingroup$ It is more tricky because even if you know the optimal number of refills from some node u to another node v and the optimal number of refills from v to a third node w, you don't automatically know how many refills are necessary to go from u to w via v. You can not just add them up since it is not clear weather a refill is necessary at v. Thus, I don't see a straight forward modification of the Floyd-Warshall algorithm. $\endgroup$ – Dennis Kraft Oct 16 '15 at 10:28
0
$\begingroup$

I think you can run BFS or DFS method $N$ times for each vertex as a source, where $N$ is the number of vertices. The thing you should consider is the fact that each state in BFS or DFS method comprises two items. The first one is the vertex number and the second is the remaining fuel. Let state $(3, 50)$ denote we are in vertex $3$, and the remaining fuel is $50$. If vertex $4$ is an adjacent vertex, and the required fuel for the path $3 \to 4$ is $60$, then refueling is required. On the contrary, if fuel for the path $3 \to 4$ was $40$, we could reach vertex $4$ with state $(4, 10)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You are not taking refills into consideration. A similar approach can be implemented like Dennis said $\endgroup$ – jjohn Oct 16 '15 at 12:03
  • $\begingroup$ @jjohn: "Let state (3,50) denote we are in vertex 3, and the remaining fuel is 50. If vertex 4 is an adjacent vertex, and the required fuel for the path 3→4 is 60, then refueling is required." Indeed, the number of refilling can be saved in each state. It is too similar to usual BFS when a value as a distance is preserved in each state. $\endgroup$ – beginner1010 Oct 16 '15 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.