0

I have successfully implemented a Dijkstra algorithm for finding optimal routes in road networks. I have constructed the data so that there are no "nodes", instead I use road segments, and the segments have links to all other connected road segments.

Turn restrictions from one road segment to another road segments are very simple to implement (if restricted turn found, then just don't add that link to the open links priority queue).

However, my road network contains more complex turn restrictions (or restricted "driving manoeuvres"):

enter image description here enter image description here

How could I take this kind of restrictions into accout with Dijkstra, where route from 0 to 5 via 1-2-3-4 is not allowed, but route from 0 to 5 via 6-7-8 is allowed? Or is this even possible with Dijkstra?

Improve this question
8
  • What exactly determines the restriction? Is it the combination of source (0) and target (5) or is it only determined by the source? Or something else? Commented Apr 15, 2024 at 11:20
  • @trincot I don't quite understand your question.. driving restrictions are specified so that you cannot travel from one segment to some other segment VIA specified segments, for example you cannot come to highway from one ramp on the left side of the highway and then exit from the next ramp nearby to right, because you would be hopping over let's say 6 lanes and cause a traffic accident.. :) Commented Apr 15, 2024 at 12:00
  • Let me put it differently. If I want to go from 0 to 2, will it be allowed via 1? If I want to go from 2 to 4, will it be allowed via 3? What exactly is the atomic restriction in your example? Commented Apr 15, 2024 at 12:03
  • Ah, yes, the only restriction here is 1-2-3-4-5, so if we start from 2, it's perfectly legal to go 2-3-4-5. Commented Apr 15, 2024 at 12:09
  • @trincot I edited the picture to give better understanding of the problem and also added another example Commented Apr 15, 2024 at 12:22
Related questions
2
Dijkstra's Algorithm Modified - Iterating on Edges?
138
Understanding Time complexity calculation for Dijkstra Algorithm
6
Dijkstra's algorithm Vs Uniform Cost Search (Time comlexity)
Load 5 more related questions Show fewer related questions

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.