Point-to-point shortest path algorithm

• US 20070156330A1
• Filed: 12/29/2005
• Published: 07/05/2007
• Est. Priority Date: 12/29/2005
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kaplan, Haim, Goldberg, Andrew, Werneck, Renato
• Application Number:
  US11/321,349
• Publication Number:
  US 20070156330A1
• Time in Patent Office: Days
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A graph is selected for preprocessing. Partial shortest path trees are constructed for the vertices of the graph and shortcuts are added to the graph to reduce the reach of certain vertices. The partial trees can be used to divide the arcs into two groups, a high reach group and a low reach group wherein a reach threshold is used to divide the groups. This threshold may be a function of the number of iterations of the preprocessing algorithm performed thus far. Upper bounds on reach of the low reach arcs are computed, and these arcs are deleted from the graph. The preprocessing algorithm is applied iteratively to the remaining arcs in the graph, with the reach threshold changing based on the current iteration. At the end of the preprocessing phase all arc reaches are below the current threshold and are deleted. The graph obtained from the input graph by adding the shortcuts, together with the reach values, may then be used during a query phase to compute shortest paths between two vertices.

Claims

1. A method for graph preprocessing comprising:

receiving a graph, the graph comprising a plurality of vertices and arcs;

generating shortcut arcs; and

computing arc reach bounds.

2. The method of claim 1, wherein computing arc reach bounds comprises:

dividing the arcs into a set of low reach arcs and a set of high reach arcs; and

removing the set of low reach arcs from the graph.

3. The method of claim 2, wherein removing the set of low reach arcs from the graph comprises removing the set of low reach arcs and replacing them with penalties.

4. The method of claim 1, further comprising:

converting arc reach bounds into vertex reach bounds;

selecting a subset of the vertices using the vertex reach bounds; and

recalculating the vertex reach bounds for the selected subset of the vertices.

5. The method of claim 4, wherein the subset of vertices comprises the vertices with the highest vertex reach bounds.

6. The method of claim 4, further comprising:

receiving a query comprising a first vertex and second vertex, wherein the first and second vertex are located in the graph; and

calculating the shortest path between the first and second vertex in the graph using the vertex reach bounds.

7. The method of claim 1, wherein the graph comprises a map.

8. The method of claim 1, wherein generating a shortcut arcs comprises:

identifying a bypassable vertex between a first vertex and a second vertex; and

generating an arc between the first and second vertex.

9. The method of claim 8, further comprising removing the bypassable vertex from the graph.

13. The system of claim 11, wherein the processor generating shortcut arcs comprises:

identifying a bypassable vertex between a first vertex and a second vertex; and

generating an arc between the first and second vertex.

10. A system for determining the shortest path between two vertices in a graph comprising:

an input device adapted to receive a source vertex and a destination vertex from a graph, wherein the graph comprises a plurality of arcs and vertices;

a storage device adapted to store preprocessing data, wherein the preprocessing data comprises vertex reach bounds and the graph with the addition of shortcut arcs; and

a processor adapted to compute the shortest path in the graph between the source vertex and the destination vertex using the preprocessing data.

11. The system of claim 10, wherein the processor is further adapted to generate the preprocessing data by:

generating shortcut arcs;

computing arc reach bounds; and

converting arc reach bounds to vertex reach bounds.

12. The system of claim 11, wherein the processor generating the preprocessing data further comprises:

selecting a subset of the vertices using the vertex reach bounds; and

recalculating the vertex reach bounds for the selected subset of the vertices.

14. The system of claim 10, wherein the graph is a map.

15. A computer-readable medium with computer-executable instructions stored thereon for performing the method of:

receiving a graph, the graph comprising a plurality of vertices and arcs;

generating shortcut arcs; and

computing arc reach bounds.

16. The computer-readable medium of claim 15, wherein computing arc reach bounds comprises computer-executable instructions for:

dividing the arcs into a set of low reach arcs and a set of high reach arcs; and

removing the set of low reach arcs from the graph.

17. The computer-readable medium of claim 15, further comprising computer-executable instructions for:

converting arc reach bounds into vertex reach bounds;

selecting a subset of the vertices using the vertex reach bounds; and

recalculating the vertex reach bounds for the selected subset of the vertices.

18. The computer-readable medium of claim 17, further comprising computer-executable instructions for:

receiving a query comprising a first vertex and second vertex, wherein the first and second vertex are located in the graph; and

calculating the shortest path between the first and second vertex in the graph using the vertex reach bounds.

19. The computer-readable medium of claim 15, wherein generating shortcut arcs comprises computer-executable instructions for:

identifying a bypassable vertex between a first vertex and a second vertex; and

generating an arc between the first and second vertex.

20. The computer-readable medium of claim 19, further comprising computer-executable instructions for removing the bypassable vertex from the graph.