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 &gt; 3 &gt; 4 &gt; 2


Because the maximum edge weight is only 2. On the other hand, the shortest path 1 -&gt; 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.