Algorithm for finding the path that minimizes the maximum weight between two nodes

Question

I would like to travel by car from city X to city Y. My car has a small tank, and gas stations exist only at intersections of the roads (the intersections are nodes and the roads are edges). Therefore, I would like to take a path such that the maximum distance that I drive between two gas stations is minimized. What efficient algorithm can I use to find that path? Brute force is one bad solution. I am wondering if there exists a more efficient algorithm.

Answer 1

Here is a simple solution:

1. Sort the edges by their weights.

2. Start adding them one by one(from the lightest to the heaviest) until X and Y become connected.

3. To check if they are connected, you can use a union-find data structure.

The time complexity is O(E log E).

A proof of correctness:

1. The correct answer is not larger than the one returned by this solution. It is the case because the solution is constructive: once X and Y are in the same component, we can explicitly write down the path between them. It cannot contain heavier edges because they haven't been added yet.

2. The correct answer is not smaller than the one returned by this solution. Let's assume that there is a path between X and Y that consists of edges which have weight strictly less than the returned answer. But is not possible as all lighter edges were processed before(we iterate over them in the sorted order) and X and Y were in different components. Thus, there was no path between them.

1) and 2) imply the correctness of this algorithm.

This solution works for undirected graphs.

Here is an algorithms which solves the problem for a directed case(it works for undirected graphs, too):

1. Let's sort the edges by their weights.

2. Let's binary search over the weight of the heaviest edge in the path(it is determined by an index of the edge in the sorted list of all edges).

3. For a fixed answer candidate i, we can do the following:

   1. Add all edges with indices up to i in the sorted list(that is, all edges which are not heavier than the current one).

   2. Run DFS or BFS to check that there is a path from X to Y.

   3. Adjust left and right borders in the binary search depending on the existence of such path.

The time complexity is O((E + V) * log E)(we run DFS/BFS log E times and each of them is done in O(E + V) time).

Here is a pseudo code:

if (X == Y)
    return 0 // We don't need any edges.
if (Y is not reachable from X using all edges)
    return -1 // No solution.
edges = a list of edges sorted by their weight in increasing order 
low = -1 // definitely to small(no edges)
high = edges.length - 1 // definitely big enough(all edges)
while (high - low > 1) 
    mid = low + (high - low) / 2
    g = empty graph
    for i = 0...mid
        g.add(edges[i])
    if (g.hasPath(X, Y)) // Checks that there is a path using DFS or BFS
         high = mid
    else
         low = mid
return edges[high]