CODEWITHSUNDEEP
algorithmgraph-algorithmdijkstrashortest-path
therealone
therealone

Reputation: 51

A Shortest path with fuel constraints

I found this problem somewhere in a contest and haven't been able to come up with a solution yet. I am thinking on the lines of applying Dijkstra's or something but it is not very clear :

''You are given a weighted connected graph of cities with all edges having positive weights. Some of the cities ( nodes ) have petrol pump whereas some don’t. You have a bike with the tank capacity of C. That is, with full tank, the car can travel for C units of distance. At any city with a petrol pump the car can fill its tank to full. Find out the shortest path between the a given source and a given destination. Assume that you start with a full tank.''

I have a feeling O(mn logn) will be accepted by it.

Upvotes: 5

Views: 7023

Answers (3)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86146

@Tim Green's method will create an exponential (in the number of gas stations) number of nodes. Running Dijkstra's over that will be very slow. There is a much faster way.

First, find the distances between all the gas stations. Also include the distances from the source to each gas station, from each gas station to the finish, and from the source to the finish. This can be done by running Dijkstra's multiple times.

This will give you a graph of all possible valid routes from start to finish. Simply run Dijktra's one more time over this graph to get the final solution.

Since each run of Dijkstra's will be O(V2) (V = number of cities) and you must run it O(G) times (G = number of gas stations, one run of Djikstra can find distance from one gas station to all other gas-stations), this algorithm will run in O(V2G) time.

Upvotes: 3

Pavel Gatnar
Pavel Gatnar

Reputation: 4053

There is a modification of Dijkstra algorithm, were the distances between gas station vertices are calculated on demand by another modification of Dijkstra algorithm, which searches all unresolved gas station vertices within a specified range.

  1. handle start and finish as gas stations.
  2. put the start into main priority queue.
  3. run main-Dijkstra with sub-Dijkstra.

main-Dijkstra performs the following steps in a loop:
0. exit when the main priority queue is empty with "finish unreachable".
1. take gas station from main priority queue.
2. exit when it is the finish.
3. call sub-Dijkstra to provide unresolved neighbour gas stations with distances to the actual one.

sub-Dijkstra searches shortest paths from the actual gas station to all vertices within fuel range using own priority queue (until the queue is empty) and handles reached gas stations based on their status:
* already resolved in main - do not process outgoing edges.
* waiting in the main queue - update distance (when lower then decreaseKey) and path
* otherwise put it into the main queue

Upvotes: 2

Tim Green
Tim Green

Reputation: 3649

Basically you need to split each node n_i to multi nodes base on the remaining fuel when bike arrived, let's call it (n_i, r). You don't need to create all (n_i, r) at the beginning, you can do it on fly.

Then similar to Dijkstra, you start from node (n_0, C), each time you can find next (n_x, r) you can reach with the smallest distance. And update all the nodes (n_y, ry) connected to (n_x, r). ry will be reset to C if n_y has a pump. And if for n_y, there is already a node (n_y, r) and r >= ry, then you don't need to create new node (n_y, ry), just ignore it.

I can not say the runtime complexity, but it should be good enough to get AC in the contest.

Upvotes: 3

Related Questions