How would I find the maximum of a set of minimum edge weights along all possibles path between arbitrary vertices (u,v)?
I was thinking a modification of Floyd-Warshall?
i.e. Path 1: s - a - b - c - d - t with weights 1 - 5 - 6 - 10 - 9
Minimum edge weight is 1
Path 2: s - x - y - z - w - t with weights 3 - 9 - 8 - 6 - 7
Minimum edge weight is 3
Thus the result is max(1, 3) = 3
Yes, a modification of Floyd-Warshall would work - instead of shortest path length, you'll keep track of maximum path "width".
If you're only interested in two vertices, you may take a simpler approach: start with an empty graph and add edges ordered by their weight (from high to low). When the nodes in question get connected, the last edge added gives you the maximal "width". Done properly (i.e. using disjoint set to check the connectedness), this will be quicker then Floyd-Warshall.
Note: I'm only considering positive weights.