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?