# shortest form $s$ to $t$ stopping at $u$

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.

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