problem:
Given two vertices of a graph,those are start point and end point and the weights of all edges in the graph are given.There are many paths exist from start vertex to end vertex.Find the weight of the minimum weighted edge that is present on each of those paths and find the maximum of those minimum weights.
input:
start point end point N — no. of edges
then N lines showing edges and their weights node1,node2,weight.
output:
out the maximum of those minimum weights .
note: the graph is connected and undirected.
http://en.wikipedia.org/wiki/Widest_path_problem
Can be solved with invariants of Dijkstra's, minimum spanning tree and Floyd-Warshall algorithms as well as some other algorithms.
Actually invariants of Dijkstra's is Prim's algorithm :)
I think there is a difference between the Widest path problem and the problem from this topic. In the first case you need to find a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. On the other hand, this problem asks you to find the weight of the minimum weighted edge that is present on each of those paths (there are many paths from start vertex to end vertex). Thus, you are asked to find the minimum weight of the edges whose removal will disconnect the start point and the end point.
Looks like author meant for each of the paths instead of what he said.
P.S. It also looks like in your interpretation we can solve problem faster and easier.
You can sort edges by decreasing weight. Then add edges into the graph until the start and end node are connected (Test this using DSU). Then to find the path you can just DFS, only using the added edges.
Edit: Another simple algorithm would be to binary search for the answer, and to check if it is possible simply DFS from start, only using edges with weight >= value.