shortest path algorithm taking into account angular deviation

Question

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.

Answer 1

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 2

This is not a definitive answer, just some references.

First, you might look at the constrained shortest-path first algorithm, about which I know little, and which doesn't look all that sophisticated. Second, the paper "Polygonal path approximation with angle constraints," 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.