Shortest Path

Hi,

I am sure most of you must be aware of dijkstra’s shortest path algorithm. Now here is a bit interesting version of it.

Problem : You are given a weighted connected graph with all edges having positive weights. Some of the cities ( nodes ) have petrol pump whereas some don’t. You have a car with the tank capacity of C. That is, with full tank, the car can travel for C units of distance. At any city with the petrol pump the car can fill its tank to full. Find out the shortest distance from a given source vertex to a given destination vertex with these constraints. Find out the shortest path between the given source and destination. Find out the shortest paths and distances from the source to all vertices.

Solution : Actually, this time, I am being a bit lazy. But I have this simple idea which certainly is a solution. Probably with a scope to improve it. Given the graph, take a vertex v without a petrol pump.  Remove this vertex and all edges incident on it. Now, for all neighbours u1,..,uk of it, add/update edges between (ui,uj). These edges can now store the shortest path between (ui,uj). Once the graph is converted in this manner, the standard algorithm can be applied. The conversion of this graph can be done in O(n^3) or O(n^4) depending upon whether we need the paths or just distances. I know I have omitted many details. But all in all, this trick can give rise to a O(n^4) algorithm ( probably O(n^3) not sure ;-) ) which does the job. Let me know if you can do better :-)

About these ads

Tags: , ,

One Response to “Shortest Path”

  1. Spring Coder Says:

    Nice problem. I am thinking on these lines.
    Let u say we have $s$ to $t$ travel that we need to find.
    Find the single source shortest path tree from $s$. Let me call something a burn order which is the ordering of all nodes as an increasing function of shortest distance from $s$.
    Note that burnOrder($s$) = 0 and butOrder($t$) need not be $n$. So a node with burnOrder=1 will be closest from $s$ and one with $i$ will be $i-1$ closest from $s$.
    Now for at each node we find all the paths that come from its predecessors. Then all we do is start from $s$ and go along each node in the burnOrder storing all paths from its predecessors as $(d, c)$ where $d$ is the distance traveled to reach it and $c$ is the fuel available till that point. When ever we have a node in burnorder with a pump, C value goes to $C$ for next step. We stop when we reach $t$ and see all the paths reaching upto $t$ and find the lowest one with $d$ and nonzero $c$.

    Sorry Complicated solution, but this will run in $O(mn)$, slightly better than $O(n^3)$.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 51 other followers

%d bloggers like this: