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.

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!

StackExchange Computer Science Q#106059, answer score: 2