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?


1 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.

  • $\begingroup$ I'm afraid the resulting graph will be too big. Is it possible to estimate the number of vertexes after replacement? $\endgroup$
    – Igor
    Commented Mar 28, 2012 at 13:59
  • 1
    $\begingroup$ @Igor: Sure, the number of vertices after replacement is twice the number of edges before replacement. If you do the variant where you only add between new vertices corresponding to edges at adjacent angles, there's one new edge for every new vertex, so the total number of edges after replacement is three times the number of edges before replacement. $\endgroup$
    – joriki
    Commented Mar 28, 2012 at 14:40
  • $\begingroup$ Can you explain the trick with adjacent angles, I don't clearly understand how it works and what's more important why it works. $\endgroup$
    – Igor
    Commented Mar 29, 2012 at 20:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .