Efficient computation of least cost paths with hard constraints

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 and comprising plural vertices and plural edges between respective vertices, 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:

• for each vertex adjacent to the source vertex, inserting into an initially empty priority queue a data item with a priority equal to the cost of the edge from the source vertex to the adjacent vertex;
• retrieving and deleting from the priority queue a minimum priority data item indicating a current edge of the graph;
• if the current edge does not terminate at the sink vertex, identifying from the searchable data structure each edge of the graph adjacent to the current edge and reachable therefrom in accordance with a predetermined condition;
• inserting into the priority queue a data item with an associated priority for each identified adjacent edge without replacing any data item associated with the identified adjacent edge that is already in the priority queue;
• deleting from the searchable data structure each vertex at which an identified adjacent edge terminates;
• continuing to retrieve a minimum priority data item from the priority queue, identify all edges reachable from the current edge, to insert a data item with an associated priority for each identified adjacent edge into the priority queue, and to retrieve a minimum priority item from the priority queue until the current edge terminates at the sink vertex;
• and
• determining the least-cost path from the priority of the data item associated with the edge terminating at the sink vertex.

A system 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 a source vertex and a 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 storage storing a searchable data structure of one or more data items respectively indicating vertices adjacent to a current vertex of the graph;
• and
• a processor inserting a data item with an associated priority of zero corresponding to the source vertex into an initially empty queue, said processor retrieving and deleting from a priority queue a minimum priority data item indicating a current vertex of the graph and having an associated priority, said processor 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 when the current vertex is not the sink vertex, said processor deleting an identified vertex from the corresponding searchable data structure, said processor 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, said processor continuing this process until the current vertex is the sink vertex, said processor determining a minimum priority from the data item associated with the sink vertex and converting the minimum priority into the least-cost path.

A system 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 a source vertex and a sink vertex, each vertex of the graph having a 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 storage storing data structure searchable for one or more data items respectively indicating vertices adjacent to a current vertex of the graph;
• and
• a processor inserting a data item into a priority queue for each vertex adjacent to the source vertex, the inserted data item having a priority equal to the cost of the edge from the source vertex to the adjacent vertex, said processor retrieving and deleting from the priority queue a minimum priority data item indicating a current edge of the graph, said processor identifying from the data structure each edge of the graph adjacent to the current edge and reachable therefrom in accordance with a predetermined condition when the current edge does not terminate at the sink vertex, said processor inserting into the priority queue a corresponding data with an associated priority for each identified edge without replacing any data item associate with the identified adjacent edge that is already in the priority queue said processor deleting from the searchable data structure each vertex at which an identified adjacent edge terminates, said processor continuing this process until the current edge terminates at the sink vertex, said processor converting the priority from the data item associated with the sink vertex into the least-cost path.

A computer-readable medium encoded with a program for finding a constrained least-cost path from a source vertex to a sink vertex in a directed graph 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 being connected by an edge to another vertex, and each edge of the graph having a corresponding cost associated therewith, said program comprising procedures for:

• (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 searchable data structure each vertex of the graph adjacent to the current vertex and reachable therefrom in accordance with a predetermined conditions
• (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 procedures (b) through (e) until the current vertex is the sink vertex;
• (g) when the current vertex is the sink vertex, determining the minimum priority from the data item associated with the sink vertex and converting the minimum priority into the least-cost path.

A computer-readable medium encoded with a program for finding a constrained least-cost path from a source vertex to a sink vertex in a directed graph representing a physical system and comprising plural vertices and plural edges between respective vertices, 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, said program comprising procedures:

• for each vertex adjacent to the source vertex, inserting into an initially empty priority queue a data item with a priority equal to the cost of the edge from the source vertex to the adjacent vertex;
• retrieving and deleting from the priority queue a minimum priority data item indicating a current edge of the graph;
• if the current edge does not terminate at the sink vertex, identifying from the searchable data structure each edge of the graph adjacent to the current edge and reachable therefrom in accordance with a predetermined condition;
• inserting into the priority queue a data item with an associated priority for each identified adjacent edge without replacing any data item associated with the identified adjacent edge that is already in the priority queue;
• deleting from the searchable data structure each vertex at which an identified adjacent edge terminates;
• continuing to retrieve a minimum priority data item from the priority queue, identify all edges reachable from the current edge, insert into the priority queue a data item with an associated priority for each identified adjacent edge, and retrieve a minimum priority data item from the priority queue until the current edge terminates at the sink vertex, and
• converting the priority from the data item associated with the sink vertex into the least-cost path.