Patent ID: 6477515
Filing Date: 2002-11-05
Classification: G06Q

Abstract:
A method for finding a constrained least-cost path from a source vertex to a sink vertex in a directed graph representing a physical system, the graph having multiple vertices located between the source vertex and the sink vertex, each vertex of the graph having a corresponding searchable data structure identifying a set of adjacent vertices, each vertex of the graph being connected by an edge to another vertex, and each edge having an associated cost, the method comprising:(a) inserting a data item with an associated priority of zero corresponding to the source vertex into an initially empty priority queue; (b) retrieving and deleting from the priority queue a minimum priority data item indicating a current vertex of the graph and having an associated priority; (c) identifying from the corresponding searchable data structure each vertex of the graph adjacent to the current vertex and reachable therefrom in accordance with a predetermined condition; (d) deleting an identified adjacent vertex from the corresponding searchable data structure; (e) inserting into the priority queue a corresponding data item with an associated priority for the identified adjacent vertex without replacing any data item associated with the identified adjacent vertex that is already in the priority queue; (f) repeating steps (b) through (e) until the current vertex is the sink vertex, and (g) when the current vertex is the sink vertex, determining the least cost-path from the minimum priority of the data item associated with the sink vertex.