Say I have an undirected weighted graph G = (V, E), and I have two vertices s and t. Now there may be a number of paths between s and t, and each path has an edge that has the maximum weight in that path. Out of all these maximum weight edges of all the possible paths, how do I find the smallest one most efficiently?
I suppose I could use a modified Dijkstra's algorithm to find all the shortest paths first, while keep record (like an array) of the maximum weight edges of all possible shortest paths, then maybe use linear time selection to find the smallest one. In this case I think I would have a running time of O((|V| + |E|) log|V|). Is this correct and is there a faster way?
Could I use Kruskal's or Prim's algorithm to find the MST of the graph, and then look at all the edges between s and t in the MST to find the largest one? I am not sure if this is correct at all.