# How to find the smallest of the maximum edges of all paths between two nodes in a graph

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.

More specifically about that required 'behaviour' of weight. The algorithm only require weight to be any type $$\mathbb{W}$$ with 'ordered monoid' structure, i.e., comes associated with an addition function $$+\colon \mathbb{W} \times \mathbb{W} \rightarrow \mathbb{W}$$ and with a unique value $$0 \in \mathbb{W}$$ such that it is associative and unital $$(a+b)+c = a+(b+c)$$ $$0+a = a+0 = a$$ and finally with a binary (partial or total) ordering relation on $$\mathbb{W}$$ satisfying $$x ≤ y \implies z+x ≤ z+y \land x+z ≤ y+z$$ You should check that the correctness proof of the shortest path algorithm only ever utilise these properties.