<p>My first guess would be to do a simple graph transformation and running the shortest-path algorithm on the transformed graph. This way, we could convert angular deviation between two roads into an additional shortest path cost along the path and thusly penalize paths involving heavy turns. </p>

<p>The conversion would go along the following lines: say, we are at some node 'n' of degree 'd'. Then, we could substitute this 'n' with a complete graph on 'd' nodes, with each node in this complete graph associated with an edge incident to 'n'. In addition, a 'u-v' edge in the complete graph would have cost proportional to the angle between the edges corresponding to 'u' and 'v'. Exactly how you set the proportion is a matter of taste: I would first try a linear function and experience with different scaling factors.</p>

CC BY-SA 3.0
2011-10-20T20:00:07.397Z
2011-10-20T20:00:07.397Z
Gabor Retvari
<p>This is not a definitive answer, just some references.</p>

<p>First, you might look at the <a href="http://en.wikipedia.org/wiki/Constrained_Shortest_Path_First" rel="nofollow">constrained shortest-path first algorithm</a>,
about which I know little, and which doesn't look all that sophisticated.
Second, 
the paper
"<a href="http://dl.acm.org/citation.cfm?id=365476&amp;dl=ACM&amp;coll=DL&amp;CFID=48724855&amp;CFTOKEN=31725648" rel="nofollow">Polygonal path approximation with angle constraints</a>,"
by Danny Chen et al. (<em>SODA</em> 2001) might be relevant. From the <em>Abstract</em>:</p>

<blockquote>
  <p>We present efficient geometric algorithms for several problems of approximating an $n$-vertex polygonal path with angle constraints in the $d$-D space for any fixed $d \ge 2$, improving significantly the corresponding graph-theoretic solutions based on known techniques. </p>
</blockquote>

CC BY-SA 3.0
2011-10-21T01:11:00.300Z
2011-10-21T01:11:00.300Z
Joseph O'Rourke
<p>I am using Floyd-Warshall(1) to compute shortest paths on a road network in order to ultimately compute <a href="http://en.wikipedia.org/wiki/Betweenness#Betweenness_centrality" rel="nofollow noreferrer">betweenness centrality</a> of road segments. At present, I am weighting the paths by metric length of road segment. I would also like to take into account angular deviation. The goal would be to favor routes that involve fewer, smaller turns (in addition to some distance weighting).</p>

<p>My attempts at writing a Floyd-Warshall or a Dijkstra that takes into account angle have not been working. Not sure whether this is just an implementation issue, or whether I am making a serious theoretical mistake in thinking that these types of shortest-path algorithms can take into account geometric properties like angle. The issue, I realize, is that to compute angular deviation, the algorithm will need a history of its previous path as it recurses through the network.(2)</p>

<p>Is this possible, and if so, any suggestions for how I can go about implementing a shortest path algorithm that takes into account angular deviation?</p>

<p>(1) I am using <a href="http://networkx.lanl.gov/reference/generated/networkx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path.html#networkx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path" rel="nofollow noreferrer">an implementation included in the NetworkX library</a> (Python).</p>

<p>(2) I found <a href="https://cstheory.stackexchange.com/questions/4853/shortest-paths-with-structured-dependence-on-earlier-path">this related question</a>, but I am afraid I cannot understand if it has any implications for my question.</p>

CC BY-SA 3.0
2011-10-21T14:45:21.157Z
can't we modify the graph so it will take them into account automatically? e.g. replace each node $v$ with $deg(v)$ clique and place appropriate weights on the edges of the clique.
Kaveh
<ds.algorithms><graph-algorithms><cg.comp-geom>
shortest path algorithm taking into account angular deviation
Drew Dara-Abrams
# shortest path algorithm taking into account angular deviation

(Asked by: username_0 on 2011-10-20)

I am using Floyd-Warshall(1) to compute shortest paths on a road network in order to ultimately compute [betweenness centrality](http://en.wikipedia.org/wiki/Betweenness#Betweenness_centrality) of road segments. At present, I am weighting the paths by metric length of road segment. I would also like to take into account angular deviation. The goal would be to favor routes that involve fewer, smaller turns (in addition to some distance weighting).

My attempts at writing a Floyd-Warshall or a Dijkstra that takes into account angle have not been working. Not sure whether this is just an implementation issue, or whether I am making a serious theoretical mistake in thinking that these types of shortest-path algorithms can take into account geometric properties like angle. The issue, I realize, is that to compute angular deviation, the algorithm will need a history of its previous path as it recurses through the network.(2)

Is this possible, and if so, any suggestions for how I can go about implementing a shortest path algorithm that takes into account angular deviation?

(1) I am using [an implementation included in the NetworkX library](http://networkx.lanl.gov/reference/generated/networkx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path.html#networkx.algorithms.shortest_paths.unweighted.all_pairs_shortest_path) (Python).

(2) I found [this related question](https://cstheory.stackexchange.com/questions/4853/shortest-paths-with-structured-dependence-on-earlier-path), but I am afraid I cannot understand if it has any implications for my question.

**Tags:** ds.algorithms, graph-algorithms, cg.comp-geom
> **Comments:**
> **username_1**: can't we modify the graph so it will take them into account automatically? e.g. replace each node $v$ with $deg(v)$ clique and place appropriate weights on the edges of the clique.  

---

## 2 answers

### Answer by username_2 on 2011-10-20. Score: 4

My first guess would be to do a simple graph transformation and running the shortest-path algorithm on the transformed graph. This way, we could convert angular deviation between two roads into an additional shortest path cost along the path and thusly penalize paths involving heavy turns.

The conversion would go along the following lines: say, we are at some node 'n' of degree 'd'. Then, we could substitute this 'n' with a complete graph on 'd' nodes, with each node in this complete graph associated with an edge incident to 'n'. In addition, a 'u-v' edge in the complete graph would have cost proportional to the angle between the edges corresponding to 'u' and 'v'. Exactly how you set the proportion is a matter of taste: I would first try a linear function and experience with different scaling factors.


---

### Answer by username_3 on 2011-10-21. Score: 4

This is not a definitive answer, just some references.

First, you might look at the [constrained shortest-path first algorithm](http://en.wikipedia.org/wiki/Constrained_Shortest_Path_First),
about which I know little, and which doesn't look all that sophisticated.
Second,
the paper
"[Polygonal path approximation with angle constraints](http://dl.acm.org/citation.cfm?id=365476&dl=ACM&coll=DL&CFID=48724855&CFTOKEN=31725648),"
by Danny Chen et al. (*SODA* 2001) might be relevant. From the *Abstract*:

> We present efficient geometric algorithms for several problems of approximating an $n$-vertex polygonal path with angle constraints in the $d$-D space for any fixed $d \ge 2$, improving significantly the corresponding graph-theoretic solutions based on known techniques.


---

