[mapserver-users] Any pointers on calculating the shortest route between 2 points?

[Adrian Popa]

Hello everybody,

Sorry if this question is not specific to mapserver, but I was wondering 
if I could get some pointers on where to start with this problem.

So, I have a layer with street numbers for some cities, and I want to be 
able to display the route between 2 such points. I've done something 
similar in the past by using Boost (as a perl module) and loading the 
network as a graph and using Dijkstra algorithm to calculate the 
shortest path between 2 points. The problem is - the data I had clearly 
defined the nodes of the graph (vertexes) and the edges (links) between 
the nodes, so I was able to easily build the graph and interpret the 
results.
The data I have now looks like this (for a record):

OGRFeature(Streets_geocoding):1123
  Name (String) = West St
  FromLeft (Integer) = 3
  ToLeft (Integer) = 5
  FromRight (Integer) = 12
  ToRight (Integer) = 32
  Link_ID (Real) =  588532637
  Judet (String) = TIMIS
  Localitate (String) = TIMISOARA
  L_PostCode (String) = 300609
  R_PostCode (String) = 300609
  Style = PEN(w:2px,c:#ff00ff,id:"mapinfo-pen-2.ogr-pen-0")
  LINESTRING (21.17921 45.751309999999997,21.18102 45.753790000000002)

The problem is I have lots of small links (street segments) but without 
an obvious way to link them together (maybe Link_ID is something useful 
- I'll look into it).

My question is: In your opinion - how is "routing" implemented on maps 
(e.g. on GPS receivers) - Do the maps have special information, or 
should I manage with what I have?

Any pointers are helpful, thanks

Regards,
Adrian