Shortest path with rotation costs.

Question

There are dotes on the plane $(x,y)$ connected with directed edges. The distance $\rho(A,B)$ is standard euclidean: $|\overrightarrow{AB}|$. Except the distance cost we pay for rotation: $k\alpha$, $\alpha$ is the angle. We need to find the shortest ("cheapest") path between to vertexes $s,\,t$.

It's sad, but triangle inequality doesn't hold true anymore. I think about smth like launching BFS from $s$ and keeping for each vertex a list of pairs (predecessor, distance). It's just an idea and I'm not sure if it'll work. Maybe it's a well known problem?

Answer 1

You could replace each vertex $v$ by vertices $v_e$, one for each edge $e$ incident at $v$, with $e$ now incident at $v_e$ instead, and connect all pairs of vertices $v_e$, $v_f$ by edges reflecting the rotation cost. Or you could reduce the number of edges by only connecting $v_e$ and $v_f$ if $e$ and $f$ are at adjacent angles. For $s$ and $t$, you could either leave them unchanged, or, if that's simpler, treat them like all other vertices and then add new vertices $s'$, $t'$ with zero-cost edges to all the vertices that $s$ and $t$ were replaced by. In any case, the problem becomes a standard problem of finding the shortest path in the resulting graph.