On Wed, 15 Jul 2009 13:30:44 -0400 (EDT) si...@mungewell.org wrote: > >> only needs an dijkstra algorithm and some more lines of code. > > > > sounds so simple... ;-) > > > > I had a look at the wikipedia page > > (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) and that > > would look to make sense.
Actually, an implementation of the Dijkstra algorithm is not difficult at all. When we were trying to do this with Python and Django, we came across a couple of sample implementations. Better yet, there is the Boost graph library which already implements the Dijkstra shortest path algorithm. The library is in C++, but there are various bindings to it. To push our own work, one can take a look at an implementation at http://citybyroad.com/ (Log in with user/password testuser/ gpstrack). This actually was a more ambitious attempt to get shortest paths based on actual travel time from GPS traces. However, ignore that for the moment, and also ignore the half- completed state of the application. Leave all the drop-down boxes as Unspecified, enter a from/to address via the auto- complete boxes (try "Raja Puri" and "Srijan Technologies", allowing the auto-complete to take over after typing a few letters), and click on the blue "FIND ROUTE" button. The result shown on the map is from the Dijkstra shortest-path algorithm, based on distance. The distance is calculated by integrating along known routes, which is a fairly tedious, manual process, but OSM routes should already have that information. For someone familiar with Delhi, the application will be unable to find some routes, as the database is not completely populated. > As you may have noticed I've actually had a relatively amount of > success with this, but my brain is off on the 'multiple targets' > question. > > Is it valid to repeat the dijkstra algorithm with multiple > 'target' nodes, so you could find the shortest path to (say) any > playground? Target nodes could auto-magically be extracted from > OSM file based on tags. [...] > Does this sound correct? Your description covers the gist of the issue. The Dijkstra algorithm actually visits every node in the network, and thus running it once between two points should find all shortest paths. In practice, it seems that the Boost implementation prunes unlikely paths, so that one has to start with two extreme points, and maybe rerun the algorithm a couple more times with other extreme points in order to get full coverage. Came into this conversation a little late, but if you had a definite purpose in mind, we would be glad to share the code, and maybe even put in some work on a reimplementation. What language are you planning on using? Regards, Gora _______________________________________________ talk mailing list talk@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk