Answered By : Joe
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.
Problem Detail: 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:
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?
Asked By : Jiew Meng
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/4942
