I have an undirected graph, where the value of the path is the maximum weight among all weights edges included in it. And I want find the path of minimum value between two given vertices in time $O(n + m)$, where $n$ - number of vertices, $m$ - number of edges.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ en.wikipedia.org/wiki/Widest_path_problem#Undirected_graphs $\endgroup$ – D.W.♦ Oct 20 '20 at 16:20
Add a comment
|
$\begingroup$
$\endgroup$
6
I will use the fact that you can check for the connectivity between two vertices $s$ and $t$ in a graph with $m>0$ edges in time $O(m)$.
Call $G$ be the input graph, and let $s$ and $t$ be endpoints of the paths you are interested in. I will denote by $G_w$ (resp. $G^<_w$) the graph induced by all the edges of weight at most (resp. less than) $w$ in $G$. You can solve the problem using the following recursive algorithm:
If $G$ has no edges, report that $s$ and $t$ are disconnected in $G$.
If $G$ has at least one edge, find the median $w$ among the edge weights of $G$, and proceed as follows:
If $s$ and $t$ are connected in $G_w$ and disconnected in $G^<_w$, return $w$.
If $s$ and $t$ are connected in both $G_w$ and $G^<_w$, apply the algorithm recursively on $G^<_w$ (notice that $G^<_w$ has at most $\frac{m}{2}$ edges).
If $s$ and $t$ are disconnected in $G_w$, build the graph $G'$ obtained from $G$ by identifying all vertices that belong to the same connected component of $G_w$, and apply the algorithm recursively on $G'$ (notice that $G'$ has at most $\frac{m}{2}$ edges, since it can't contain any edge with weight less than or equal to $w$).
The time complexity of the above algorithm is described by the recurrence equation: $T(m) = T(m/2) + O(m)$, which has solution $T(m)=O(m)$.
This problem is the same as its maximization version once all edge weights are multiplied by $-1$.
-
$\begingroup$ You can explain what the cases mean: "Otherwise", "If this is not the case"? How do these cases differ? $\endgroup$ – Kapa Apr 26 '20 at 11:20
-
$\begingroup$ I explicitly stated the condition for each of the cases. Is this clear now? $\endgroup$ – Steven Apr 26 '20 at 12:50
-
$\begingroup$ Everything is clear, but what is the difference between $G_w$ and $G_w^{<}$ $\endgroup$ – Kapa Apr 26 '20 at 14:13
-
$\begingroup$ $G_w$ is the graph induced by all the edges of weight at most $w$ in $G$. $G^<_w$ is the graph induced by all the edges of weight smaller than $w$ in $G$. An edge of weight $w$ is in $G_w$ but not in $G^<_w$. $\endgroup$ – Steven Apr 26 '20 at 14:27
-
$\begingroup$ Maybe I'm wrong, but we run the procedure twice at each stage, and the recurrence equality will be different. $\endgroup$ – Kapa Apr 29 '20 at 21:16
