[Routing] Find shortest path using OSM format file for a country.

[Curt Nowak]

Hi Oleg,

in order to get a well connected graph (i.e. a graph in which every node is reachable from every other node in that graph) I use the follwowing procedure:

FOR EACH node n in the graph
    IF node does not belong to a cluster yet
        DO
            one iteration of the Dijkstra algorithm (start node being n)
            assign every newly reached node to current_clusterID
        WHILE there are still nodes reachable "via Dijkstra algorithm"
    END IF
    current_clusterID := current_clusterID + 1
END FOR

If your map contains m disjunct well connected graphs, you will end up with m clusters.
Then I simply delete all but the largest cluster. In my findings (map of Germany) this main cluster contains ~99% of the nodes if I remember correctly, so I don't really mind deleting the rest.

Curt



-----Ursprüngliche Nachricht-----
Von: routing-bounces at openstreetmap.org [mailto:routing-bounces at openstreetmap.org] Im Auftrag von Oleg Demchenko
Gesendet: Sonntag, 20. Juni 2010 21:21
An: routing at openstreetmap.org
Betreff: [Routing] Find shortest path using OSM format file for a country.


Hi All.
I have a task to develop Java application on Windows server which estimates shortest path available for vehicle between any coordinates given within country. Distance between coordinates could be from 400m to 250 Km.

I've spent several weeks for the following idea: country shape file from CloudMade  loaded to PostGIS db, graph (build from features/LineString, DirectedLineString) using appropriate line builders. Than DijsktraShortestPathFinder. Well, I even developed a method which split LineString on "simple" line segments (if it rings or segments) and intersect them each other using spatial index. But graph connects nodes and find a path for points 10-15 km each other. For bigger distance and bigger number of lines it do not connect them all properly while building a graph and DijsktraShortestPathFinder can't find a path.

Afterwards GEOTools and OSM developers advised me to use OSM format files, because they already contains nodes, ways, relations, etc. I've load   country highway DB to PostgreSQL using OSMOSIS API v1.6

Could you advice, please,  me how to build well connected graph and/or find a route on reliable basis?
One of the options I've found is Traveling Salesman with Route class. It is possible to load OSM file from  disk. But how to build a graph afterwards and how mySelector below should be implemented?

FileLoader fl = new FileLoader(new File("C:\\Install\\denmark.osm.highway"));
 MemoryDataSet map = fl.parseOsm();
 LatLon startCoord = new LatLon(12.180064, 55.470843);
 Node startNode = NodeHelper.findNearestNode(osmData, startCoord);

 LatLon targetCoord = new LatLon(12.198208, 55.516831);
 Node targetNode = NodeHelper.findNearestNode(osmData, targetCoord);

 TurnRestrictedMultiTargetDijkstraRouter router = new TurnRestrictedMultiTargetDijkstraRouter();
 Route theRoute = router.route(map, targetNode, startNode, mySelector);
 ...



--
All the best
              Oleg Demchenko