Shortest path preventing particular edge combinations

1
votes

I have been using networkX to compute the shortest path distance between two points A and B in a graph thanks to Dijkstra's algorithm. The edges of my graph represent road segments, and the nodes the connections between segments. The weight function is the segment length, so that the returned path distance is the actual geographical distance.

However, the calculated paths are sometimes unrealistic for my use. More specifically, I would like to prevent the algorithm from using paths implying very sharp turns between two successive edges. This implies that the weight of a particular edge is a function of the edge itself, but also of its precedessor in the path (so that the turn angle can be computed and sharp turns dismissed).

As a (simplistic) example, let's consider the below graph (assuming that the nodes and represented according to their actual geographical position). For the sake of simplicity, each edge has a weight (or distance) equal to 1. The shortest path from A to B is shown in green, and the corresponding distance is 2.

Shortest path without "sharp turn" constraint

However, the proposed path involve a sharp turn at node C (which can be detected based on the geographical coordinates of nodes A, B and C). This kind of turn should be forbidden, such that the proposed shortest path becomes the one described below.

Shortest path with "sharp turn" constraint

The distance is now 6, but the path avoids the transition A-B-C which involved a sharp turn.

What do you think are my options to implement such requirement?

1
networkxshortest-pathdijkstra
I'm guessing each node has a coordinate. Can you share a minimal example, and an expected output? Also please clarify what can be considered as a "sharp turn" - yatu
Question has been edited with an example. The definition of "sharp turn" would be based on the heading difference between 2 successive edges above a defined threshold. However, on a more generic perspective, the question is rather about the definition of edge weight based on its predecessor in the path. - G. Vaurs
You could implement a method to calculate the cost on the fly based on the two connected nodes (say B and C) and the previous node (A). If going from A to B and C involves a sharp turn, make the cost infinite. - c0der
Indeed, I can technically implement a weight function that would calculate the weight from B to C considering the predecessor of B. However, I have the feeling that doing so would prevent the algorithm from working as expected. As an example, if B has several potential predecessors (let's say A1 and A2), and the shortest path to B is obtained by passing through A1, the algorithm will store A1 as the predecessor of B. Now, if the next edge is C and (A1-B-C) is not possible as it involves a sharp turn, the algorithm will never try to consider A2 as a possible predecessor of B. - G. Vaurs
Tip: adding @username (i.e @c0der) to a message alerts the user of that message. I think you need to store only the fixed weight of B-C and add to it, on the fly (calculate) additional cost that is angle dependent. - c0der

1 Answers

0
votes

I have done something similar by making it a multi edge graph. Such as there is more than one edge between any two nodes. The 2nd edge in your case could be a numerical value identifying the orientation of the edge(road).

Considering south to north as 0, you could assign -180 to 180 to each orientation and then your algorithm need only compute the difference between the two weights of these edges to figure out if the node is sharp turn and thus eliminate it.

Look up “multgraph” or “multidigraph” in networkx api for implementation

One edge has to be distance other has to be orientation, encoding both orientation and distance to a single weight will require trignometric coding from a central (0) point