Given two places in a specific region, how can I compute a path that is of certain distance (the distance is given as a parameter) which connects the two places. The resulting path should ideally be composed of roads that are visited no more than once.

I have learnt that this problem can be seen as a graph problem where the roads in the map represent the edges of the graph and the intersection/junctions represent the nodes of the graph. From this we can simplify the problem to finding a path of certain length for any two nodes in the graph.

One of my approaches to this problem can be broken into two steps:

  • Finding the shortest path between the two nodes (using A* or a similar algorithm).
  • Extending/Expanding the shortest path that is returned from A* so that it's long enough.

Now, I am not exactly sure if this approach is worth pursuing or if a better approach exists? Also, I've not come across any methods that would allow me to expand the path - are there any specific techniques that can achieve this?

asked 16 Jan '13, 23:28

Sadeer's gravatar image

Sadeer
1768914
accept rate: 0%


https://wiki.openstreetmap.org/wiki/Routing#Developers may be of interest for you, if you did not know

permanent link

answered 17 Jan '13, 00:44

aseerel4c26's gravatar image

aseerel4c26 ♦
32.1k16239551
accept rate: 17%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×419
×138
×68
×16

question asked: 16 Jan '13, 23:28

question was seen: 3,954 times

last updated: 17 Jan '13, 00:44

powered by OSQA