Gas Station Problem

Find a starting station to complete the tour. Reset start whenever the running surplus becomes negative. If total gas ≥ total cost, the solution exists.

Algorithm Steps

Track running surplus of gas-cost.
When surplus < 0, reset start to next station and surplus to 0.
At end, if total ≥ 0, return start; else no solution.

Speed (ms)

Station 0

gas=1, cost=3, diff=-2

Station 1

gas=2, cost=4, diff=-2

Station 2

gas=3, cost=5, diff=-2

Station 3

gas=4, cost=1, diff=3

Station 4

gas=5, cost=2, diff=3

Start index: 0

Running surplus: 0

Total (sum diffs): 0

When surplus goes below 0, start moves to next station.

Pseudocode

1procedure GAS_STATION(gas, cost)
2  start ← 0; surplus ← 0; total ← 0
3  for i from 0 to n-1 do
4    diff ← gas[i] − cost[i]
5    surplus ← surplus + diff; total ← total + diff
6    if surplus < 0 then
7      start ← i + 1; surplus ← 0
8    end if
9  end for
10  if total ≥ 0 return start else return −1
11end procedure

Practice Problems

Use Cases

Round-trip feasibility with refueling constraints.
Battery range checks for delivery/EV routing loops.
Production lines balancing (surplus/deficit propagation).

Back to Dijkstra Shortest Path