H - Electricity – 04 – L
Patent
H - Electricity
04
L
H04L 12/56 (2006.01)
Patent
CA 2746322
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.
Les modes de réalisation de la présente invention concernent des systèmes et procédés qui permettent de trouver la route la plus rapide entre deux emplacements sur un graphique avec des contraintes de contours multiples d'une manière efficace, à la fois temporellement et spatialement. Dans certains modes de réalisation, l'algorithme de Dijkstra est séparé en univers distincts lorsque a) une contrainte de contours multiples est obtenue, et b) le long de chaque contour d'une contrainte de contours multiples. Dans certains modes de réalisation, la séparation est effectuée afin de trouver la route la plus rapide (à savoir, ayant la plus faible pondération) jusqu'à l'intersection ou aux intersections à la fin des contraintes. Ces univers, dans certains modes de réalisation, sont fusionnés ou supprimés lorsque l'intersection à la fin de la contrainte est rencontrée. En utilisant ces systèmes et procédés, dans certains modes de réalisation, le trajet le plus court entre deux emplacements d'un réseau de routes à contraintes de contours multiples peut être déterminé de manière efficace.
Cereke Carl
Mason Ralph
Mitchell David
Sim & Mcburney
Telogis Inc.
LandOfFree
System and method for efficient routing on a network in the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for efficient routing on a network in the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for efficient routing on a network in the... will most certainly appreciate the feedback.
Profile ID: LFCA-PAI-O-1862360