Dijkstra with max instead of sum

Question

Is it true that if we replace in the Dijkstra algorithm + with max, then the resulting algorithm correctly solves the problem of finding the shortest paths where the length of the path is measured as the maximum of its edge weights?

Answer 1

Yes, it is true.

Let $w: E(G) \to \mathbb{R}$ be a weight function on the edges of $G$, $s \in V(G)$ be the start vertex. Let $p(v) = \min\{\max\{w(e_1), \ldots, w(e_k)\} \mid e_1, \ldots, e_k \text{ is edges of a path from } s \text{ to } v \}$ i.e. the shortest path between $s$ and $v$.

Let's prove by induction on the step of Dijkstra's algorithm that it does indeed find the shortest paths. Let $S \subseteq V(G)$ be the set of vertices that have been already processed by the algorithm. Then Dijkstra's algorithm finds $p'(v) = \min\{\max\{p(u),w(uv)\} \mid u \in S\}$ for every $v \in V(G) \setminus S$. Then it is sufficient to prove that there exists $v_0$ such that $p(v_0) = \min p'(v)$ the equality $p(v_0) = p'(v_0)$ holds. Let $e_1, \ldots, e_k$ be the edges of the shortest path from $s$ to $v_0$. $e_k = u v_0$ then $p(u) \le p(v_0)$. If $u \in S$ the statement is proved. Otherwise pick $v_0 := u$ instead (this reduction is finite since we can choose a vertex closer to $s$ in terms of the smallest number of edges in a path between them).

So essentially nothing changes comparing to the algorithm and the proof.

But there is another solution that uses Disjoint Set Union (DSU) data structure. Initialize DSU with sets $\{v_1\}, \{v_2\}, \ldots, \{v_n\}$. Then add edges in the increasing order of $w$ and when an edge $uv$ is added unite the sets containing $u$ and $v$ in the DSU. If at some step an edge with a weight $x$ has been added last then all the vertices in the set containing $s$ have distance to it at most $x$. So if you unite sets $A \ni s$ and $B$ put $p(v) = x$ for $v \in B$.