"Given a connected undirected weighted graph, find the maximum weight of the edge in the path from s to t where the maximum weight of the edges in the path is the minimum."
This seems like a Floyd–Warshall algorithm problem. Is there an approach faster than O(V^3)?
I submit that a breadth first search (BFS) to determine whether s is connected to t by any path can run in O(V) time, since each vertex need only be visited once.
I propose therefore, that the solution to this problem is to sort the edges by weight, and then
while the BFS succeeds in finding a path from s to t
remove the highest weighted edge from the graph
The last edge to be removed before the BFS fails is the maximum weighted edge that you're looking for.
Total running time is O(E log E) to sort the edges by weight, plus O(VE) to run the BFS until removing an edge disconnects the graph.