# Finding paths with smallest maximum edge weight

I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge.

In the above graph, the easiest path from 1 to 2 is:

1 > 3 > 4 > 2


Because the maximum edge weight is only 2. On the other hand, the shortest path 1 -> 2 has maximum weight 4.

So it's an MST problem. I am thinking I will use Kruskal's algorithm to build the tree, but I'm not sure how exactly. I will know the edges but how do I "reconstruct" the path? For example, given vertices 3 and 2, how do I know to go left (top) of right in the tree? Or do I try both ways?

• This problem is known as widest path (or bottleneck shortest path) problem (in its minimax flavor). Wikipedia has plenty of references to algorithms. – Raphael Oct 8 '12 at 8:57
• Oh, there was a duplicate. – Raphael Oct 8 '12 at 20:19
• Note that this can be done in linear time (faster than finding an MST). The basic idea is to binary search for the minimum K such that deleting edges of cost more than K leaves the graph connected. In addition, when you query a K and determine that it is big enough, you delete all edges of cost greater than K. When you query a K and determine it is too small, you contract all edges that have cost at most K. (You use median finding on the remaining edge costs to find the K to query.) – Neal Young Nov 21 '12 at 21:50

• Ok, its said that the possible source vertices is small (only 10 possible start vertices). So now what? Build a table of 10 x (total num of vertices) and populate them with the max weight to that vertex? by transversing the tree from each possible source vertex? – Jiew Meng Oct 8 '12 at 7:38