Patent ID: 7437239

Claim:
A method for determining the minimal cost path between two points (A,B), via a transport network comprising a plurality of nodes (P n ) which are connected in pairs by segments, the method comprising the steps of: attributing a cost to each segment of the network; developing two path graphs, substantially starting from two points (A,B); classifying the segments according to a plurality of network levels and for each network level, attributing a predefined threshold of number of segments of said level; during the development of at least one of the two graphs; searching a group of successive segments with a given level m, comprising exclusively intermediate nodes which do not belong to any segment with a level which is greater than or equal to m, other than those of the group of successive segments with the level m concerned; and the group of successive segments is substituted by a single segment with a level m; calculating the number of segments of the graph of a lowest level m inf , if the number of segments of the graph developed of a lowest level minf is equal or greater than starting from a predefined threshold of number of segments of level m inf , said at least one of the two path graphs is developed taking into account only the segments which belong to the levels which are strictly higher than the level m inf , the number of segments of the graph developed of a lowest level m inf +1 is calculated; if the number of segments of the graph developed of a lowest level m inf +1 is equal or greater than a predefined threshold of number of segments of level m inf +1, said at least one of the two path graphs is developed taking into account only the segments which belong to the levels which are strictly higher than the level m inf +1; interrupting the development of the two path graphs when they comprise at least one first common interference node (P i ); determining two minimal cost paths belonging respectively to the two path graphs; and connecting said two minimal cost paths in order to obtain a minimal cost path connecting the said two points (A,B).