# shortest path algorithm taking into account angular deviation

I am using Floyd-Warshall(1) to compute shortest paths on a road network in order to ultimately compute 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 (Python).

(2) I found this related question, but I am afraid I cannot understand if it has any implications for my question.

• 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. Oct 21, 2011 at 14:45

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.