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

Question

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.

Answer 1

In biref, you can just replace addition function with max function everywhere in the typical shortest path algorithm and it will work because they 'behave' the same way and that the algorithm only ever require the weight (together with the aggregation function) to have that 'behaviour'.

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.

For fun, you could weight the edges of graph by string, add them using concatenation, have empty string be unit of concatenation, and ordered them lexicographically. Now you can find which path between 2 given points spells out the earliest word in dictionary using shortest path algorithm!