1
$\begingroup$

Given an undirected weighted graph $G$ and two vertices $s, t$. We want to find a path $P$ from $s$ to $t$ that minimizes the following objective function $L$

$$L(P) = max(len(P), max\{c(e) \mid e \in P\})$$

For example, consider the following graph

enter image description here

Here we have two ways to go from the green node to the red node. Either with the left path or the right path. Here we choose the left path because $L(\text{left path}) = max(6, 2) = 6$ and $L(\text{right path}) = max(3, 7) = 7$.

Initially, I thought the problem can be solved easily by doing breadth-first search. However, the standard BFS would not work. For example, consider another graph

enter image description here

For this graph, the optimal path from $a$ to $g$ is $(a, d, e, f, g)$ with a goodness of $max(4, 4) = 4$. However, this path is not optimal to go from $a$ to $d$. For minimal cost from $a$ to $d$ we need to go $(a, b, c, d)$ with a cost of $max(3, 3) = 3$ instead of $(a, d)$ with a cost of $max(4, 1) = 4$.

In conclusion, the algorithm does not work because a sub-path of an optimal path does not have to be optimal.

Any hint for this problem would be highly appreciated.

$\endgroup$

1 Answer 1

5
$\begingroup$

Let's restrict ourselves to the case in which $s$ and $t$ are connected in $G$ and the length of the shortest path from $s$ to $t$ in $G$ is not larger than the maximum edge cost (otherwise the problem is trivial).

Consider this simpler problem first: Given an integer $c$, return the length $\ell(c)$ of the shortest $s$-$t$ path in the subgraph $G_c$ of $G$ induced by all the edges with cost at most $c$. If $s$ and $t$ are not connected in $G_c$ then $\ell(c) = +\infty$.

Clearly this problem can be solved in time $O(m + n \log n)$ using Dijkstra's algorithm, where $n$ and $m$ are the number of edges and vertices of $G$, respectively.

Let $c_1, c_2, \dots, c_k$ be the costs of the edges in $G$, in increasing order (no repetitions) and let $c_0 = -\infty$. Notice now that $\ell(c_i)$ is monotonically non-increasing with respect to $i$. Hence, if $j \ge 1$ is the smallest value of $i$ for which $\ell(i) \le c_i$, you have that the optimal solution to your problem has cost $\min\{ c_{j}, \ell(c_{j-1}) \}$.

The value $j$ can be found by binary searching over $c_0, c_1, c_2, \dots, c_k$. Since there are at most $m$ distinct costs, this requires computing $O(\log m) = O(\log n)$ values $\ell(\cdot)$ and the overall time complexity is $O(m \log n + n \log^2 n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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