Consider a weighted directed network with edge costs cij , where nodes represent cities and edges roads. Each cost cij represents the fuel consumption of a vehicle driven on that road. There is a petrol station in every city with a free unlimited supply of fuel, but no petrol stations between cities. Describe an efficient method to determine, for every pair of cities ni , nj , the minimum size of a fuel tank that would allow a vehicle to drive from ni to nj.