The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 11, 2014
Filed:
Jun. 17, 2011
Carl David James Cerecke, Christchurch, NZ;
David John Mitchell, Christchurch, NZ;
Ralph James Mason, Christchurch, NZ;
Jason Koch, Aliso Viejo, CA (US);
Howard Jelinek, Aliso Viejo, CA (US);
Carl David James Cerecke, Christchurch, NZ;
David John Mitchell, Christchurch, NZ;
Ralph James Mason, Christchurch, NZ;
Jason Koch, Aliso Viejo, CA (US);
Howard Jelinek, Aliso Viejo, CA (US);
Telogis, Inc., Aliso Viejo, CA (US);
Abstract
Embodiments provide systems and methods that find the quickest route between two locations on a graph with multi-edge constraints in a time and space efficient manner. In some embodiments, Dijkstra's algorithm is split into separate universes when a) a multiple-edge constraint is reached, and b) along each edge of a multi-edge constraint. In some embodiments, the split is performed for the purpose of finding the quickest (i.e. lowest weighted) route to the intersect ion(s) at the end of the constraints. These universes, in some embodiments, are merged or discarded when the intersection at the end of the constraint is found. Using these systems and methods, in some embodiments, the shortest path between two locations of a multi-edge constrained road network can be efficiently determined.