Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have this question: Given a strongly connected and directed graph $G = (V,E)$ with positive weights define $E(t)$ to be the group of edges whose weight is at most $t$. Find an algorithm that calculates the minimal $t$ such that $G(t) = (V,E(t))$ is strongly connected.
I thought about running Dijkstra $v$ times from every vertex and then all of the edges will be the minimal $t$ but I am not sure the time complexity is the best. Is there a better solution for this problem?
We can solve the problem in $\mathcal{O}(E \log V)$ by binary search.
We can identify the strongly connected components in a graph in linear ($\mathcal{O}(V + E)$) time. Thus we can check if the graph is strongly connected in linear time.
If $G(t_{0}) = (V, E(t_{0}))$ is strongly connected, so is $G(t) = (V, E(t))$ for $t \geq t_{0}$. Further, if $G(t_{0})$ is strongly connected, so is $G(t)$ where $t$ is the maximum edge weight that is at most $t_{0}$. Thus we can binary search for $t$ over all edge weights.
The algorithm is:
In the binary search, we maintain the invariant that $G(w_{h})$ is strongly connected (or $h = |E| + 1$), while $G(w_{l - 1})$ is not (assuming $|V| \geq 2$). We exit the loop when $l = h$, thus either $l = |E| + 1$ and the graph is not strongly connected for any $t$, or $G(w_{l})$ is strongly connected, but $G(w_{l-1})$ is not, thus $G(t)$ is not strongly connected for $t < w_{l}$. Thus the algorithm is correct.
The first step takes $\mathcal{O}(E \log E)$ time. The third step takes linear time and is executed at most $\log E$ times. Thus, the complexity is $\mathcal{O}((V + E) \log E) = \mathcal{O}(E \log V)$.
