Minimum Weighted Path Tree of an Undirected Graph

Question

Assume that we have an undirected graph G=(V,E) and we have two nodes S and X.

1. Can we come up with an algorithm such that the largest weight of the edge on the path from S to X is minimized? Note that it is not the shortest path algorithm since we are not interested in minimizing their sum.
2. What is the complexity of this algorithm?
3. Is the minimum spanning tree algorithm (such as Prim) is a solution for the problem?

Answer 1

I don't know if minimum spanning tree will solve it or not, but it's certainly solvable by making some modifications to Dijkstra's algorithm.

Define the "length" of a path as the maximum edge in that path. Now find the shortest path from S to X using Dijkstra's algorithm. This is the path you are looking for. Complexity is O((N+M)log N) if you use a binary heap and O(N * log N + M) with a Fibonacci heap.

Note that for this new definition of path length, if the length of a path is l, then adding an edge to the end of the path will not decrease it's length, since the maximum edge in that path can only increase. This property is necessary for Dijkstra's algorithm to work correctly.

For instance, if you were looking for the path with the shortest edge, then Dijkstra's algorithm will fail just like it fails when there are negative edges in the graph.

Answer 2

You can use minimum spanning tree (Prim's algorithm) to solve this problem. You will start with vertex S, then continue to build the tree using Prim's algorithm until you find X. Complexity will be O((V+E)*logV).
It will work because in the prim's algorithm you always choose the edge with minimum weight first.