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?