Suppose you want to go from vertex $s$ to vertex $t$ in an unweighted graph $(V, E)$, but you would like to stop by vextex $u$ if it is possible to do so without increasing the length of your path by more than a factor $\alpha$. Find an efficient algorithm that would determine an optimal $s-t$ path given your preference to stopping at $u$ along the way if doing so is not prohibited costly.

Here is my try :

First perform a BFS from $s$. When you get at $t$ you know what is the shortest past in $G$ from $s$ to $t$. We denote the size of this shortest path by $P$. Now we perform an other BFS from $s$, when we get at $u$ we know what is the shortest path $M$ from $s$ to $u$. Once again we perform a BFS from $u$ and when we get at $t$ we know what is the shortest path $K$ form $u$ to $t$. If $\mid M \mid+\mid K \mid \leq \alpha P$ then the optimal path $(M,K)$ is a solution. So we are performing $3$ times a BFS in $G$, thus the overall complexity is $O(X + Y)$ where $X$ is the number of edges and $Y$ the number of vertex.

Is it possible to do better? Is what I said correct?


What you said is true.

Using your notations:

$P$ : path from $s$ to $t$

$M$ : path from $s$ to $u$

$K$ : path from $u$ to $t$

Notice that $P,M,K$ are all shortest paths from their respective sources to their targets.

Following the logic above:

$M \cup K$ is the shortest path from $s$ to $u$ to $t$

hence if $|M \cup K|$ is a good enough result for you - accept it. If it's not, i.e $|M \cup K| > \alpha|P|$, then essentially no shorter path exists from $s$ to $t$ using $u$.

(you can try proving $|M \cup K| \geq |P|$, may help your intuition!


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.