5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Your alternative approach seems to be Kruskal's algorithm, for minimal spanning tree. Interesting. $\endgroup$ – Hendrik Jan Dec 11 '19 at 2:01
  • $\begingroup$ Yep, that's correct! That means that for this metric we can find the shortest path tree in $\mathcal{O}(|E| \log |E|)$ time independently of the starting vertex $s$. $\endgroup$ – Artur Riazanov Dec 11 '19 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.