CODEWITHSUNDEEP
graph-theorydynamic-programming
Roy
Roy

Reputation: 867

Shortest path with a fuel tank

This is an homework question and I'd be happy for some guidance.

Let G=(V,E) be an undirected graph where each vertex represents a city, and the edges have weights that represents travel distances. Some of the cities have gas stations in them. A car starts from vertex s with a gas tank sufficient to travel length L. I need to find the shortest path between s and t so that the car won't run out of gas.

My main thought was to use Floyd–Warshall algorithm with some changes. When we calculate shortestPath(i,j,0) we assign w(i,j) if i has a gas station and L-w(i,j) > 0 , and infinity otherwise. However, for the next steps, I don't know how to add the current fuel status into the calculations.

Thanks.

Upvotes: 2

Views: 4220

Answers (1)

Ante
Ante

Reputation: 5448

Make new weighted graph with vertices: s, t and cities (C) with gas station.

Edges:

  • s-c, with c from C, if there is a shortest path between s and c has length <= L,
  • c1-c2, with c1, c2 from C, with length c1-c2 <= L,
  • c-t, with c from C, with length c-e <= L,
  • s-t, if length s-t <= L.

And edge weight set to length v1-v2.

Standard Dijkstra on this graph should return skeleton of shortest path you are looking for on original graph.

It is possible to crate new graph 'iteratively' when Dijkstra asks for edges on boundary vertices. Something like, first create s-c and s-t edges (and vertices), and if there is a demand for c1-c2 and c-t than add these vertices and edges to a graph.

Upvotes: 4

Related Questions