Method and device for determining the length of a shortest path in a network

1. A computer-implemented method for pre-processing a road network, wherein the road network comprises nodes and edges, each edge having a length measured according to a given metric, the method comprising the steps of:

selecting a source and a target node;

determining a transit node for the selection, wherein the transit node is a node on the shortest path between the source node and the transit node and is determined based on a partition of the network into cells;

determining a length of a shortest path between the source node and the transit node; and

storing the length in a computer-readable medium.

2. The method of claim 1 , wherein the partition of the network into cells is based on a geometric grid.

3. The method of claim 2 , further comprising the step of determining a set of transit nodes for a cell.

4. The method of claim 3 , wherein determining the set of transit nodes for a cell comprises a vertical and a horizontal sweep of the grid.

5. The method of claim 1 , wherein the set of transit nodes for a cell is determined based on a set of transit nodes determined with respect to a finer grid.

6. The method of claim 3 , wherein the length of an edge is measured in terms of geographical distance.

7. The method of claim 5 , wherein the length of an edge is measured in terms of travel time.

8. Computer-readable medium, storing a network pre-processed according to one of the preceding claims.

9. A method for determining the length of a shortest path between a source and a target node in a road network, the method comprising the steps of:

determining a first closest transit node for the source node; and

determining a second closest transit node for the target node,

such that the sum of the lengths of the paths between the source node and the first transit node, between the first transit node and the second transit node, and between the second transit node and the target becomes minimal, wherein the lengths are precomputed and determined from a computer-readable memory.

10. Method according to claim 9 , further comprising the step of deciding whether the source and the target node in the network are local with respect to each other.

11. The method of claim 10 , wherein the length of a shortest path is determined using the Dijkstra-Algorithm, if the source and the target node are local with respect to each other.

12. A method for determining a shortest path between a source node (src) and a target node (trg) in a network, wherein each node v on the shortest path is identified by the property

d ( u,trg )= l ( u,v )+ d ( v,trg ),

wherein

d(u, trg) is the length of the shortest path from a node (u) to the target node, wherein the node (u) is already known to lie on the shortest path (initially u=src);

l(u, v) is the length of the edge between u and v;

d(v, trg) is the length of the shortest path from v to the target (trg); and

wherein the distances (d) are determined using a method according to claim 11 .

13. The method according to claim 12 , further comprising the step of outputting the path on a display device.

14. The method according to claim 13 , wherein the transit nodes on the path are explicitly marked.

15. A device for determining the length of a shortest path between a source node and a target node in a network, comprising:

an input control unit;

a network information access control unit;

a central memory;

a transit node determination unit, wherein the transit node determination unit comprises a first subunit for determining a first closest transit node for the source node; and a second subunit for determining a second closest transit node for the target node, such that the sum of the lengths of the paths between the source node and the first transit node, between the first transit node and the second transit node, and between the second transit node and the target becomes minimal, wherein the lengths are precomputed and determined from a computer-readable memory; and

a display controller.

16. Use of the computer-readable medium of claim 8 in a navigation device.