Posts Tagged ‘weighted graph’

Shortest Path

December 3, 2010


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 🙂