GROUP: shortest-path
An algorithm for finding the least-cost path from an origin to a destination. In dynamic models, a time-dependent shortest path algorithm is used, which accounts for variation in costs and available links minute-to-minute or second-to-second rather than assuming a static cost and availability over a lengthier time period.
Terms
A the shortest path computation that starts at the destination node. This is used when there is a preferred arrival time.
A node that is reachable from a node (forward shortest-path) or a node that can reach the current node (backward shortest path)
Links coming into or going out of a node.
A shortest path computation that starts at the origin node. This is used when there is a preferred departure time.
The ordered queue that contains stops with stop states that need to have their costs updated in order to find the shortest path. Stops are processed in order of cost, with least cost stops processed first.
The process of initializing the label stop queue, updating, and then finalizing the stop states. The origin or destination state now has a label that has a cost that encapsulates the costs of all the trip links and transfers, but with inaccuracies regarding the timing of the non-transit links, which must be updated using path enumeration.
The process of initializing the label stop queue, updating, and then finalizing the stop states. The origin or destination state now has a label that has a cost that encapsulates the costs of all the trip links and transfers, but with inaccuracies regarding the timing of the non-transit links, which must be updated using path enumeration.
In the context of a shortest path algorithm, stops are labeled with the overall generalized cost of travelling from that stop to the destination (in a forward shortest-path) or from that stop to the origin (in a backwards shortest-path). Stops can be iteratively updated throughout the algorithm.
When all stops are removed from the label stop queue, the final costs for the destination (in forward-shortest-path) or origin (in backward-shortest-path) is finalized based on the cost labels of the emanating egress or access links.
The first step of a shortest-path algorithm. Stop labels should be initialized to be greater-than or equal to their final cost and should allow for the greatest number of emanating links (i.e. for a walk access link in a forward-shortest-path, assume it is as early as possible). All stops are added to the label stop queue.
Updating stop states when a stop is removed from the label stop queue.
The combination of a stop label (l) and upstream (forward shortest-path) or downstream (backward shortest-path) links (Pa).
A link that is reachable from a node (backward shortest-path) or a link that can reach the current node (forward shortest path)
A node that is reachable from a node (backward shortest-path) or a node that can reach the current node (forward shortest path)
Related Articles
Other Categories