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?

You're right; it's essentially a MST problem. First build the minimum spanning tree, then use breadth-first or depth-first search to find the unique path in the tree between the two vertices.

StackExchange Computer Science Q#4942, answer score: 5