Re: Reply: Time dependent shortest path

For the single-pair problem (shortest path from A to B), take the graph
whose nodes, n', correspond to node/time (n,k) in the orignal graph and
find the shortest path from (A,0) to (B,t) for some t. This can be
practical. The n' graph has lots of nodes, but the number of edges
only goes up linearly with k. You also don't need to actually put an
n' node or edge into memory until you actually reach it. Any
single-source shortest-path algorithm that can take advantage of this
situation may be appropriate.

If you can precompute a fairly tight lower and upper bound on the time
of the shortest path (I don't believe you said that time and cost were
the same) then in some cases you may save some computation by
simultaneously searching forward from (A,0) and backwards from (B,x)
for all of the feasible 'x' candidates for the shortest solution.

If cost and time are the same (or closely related), it can also make
sense to look for choke points that must be traversed. If any path
from A to B must go through either C or D, then the quickest path from
A to B will include either the quickest path from A->C or the quickest
path from A->D. Having reached C and D, you no longer need to consider
visiting nodes that are on the wrong side of the choke point. For many
problems you can identify choke points with a time-independent analysis
of the original graph.

HTH

.

Relevant Pages

  • Re: Shortish paths
    ... original graph. ... The functionality of Dijkstra's original algorithm can be extended ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Shortish paths
    ... For how many nodes and how many edges will the actual algorithm run ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Representing a Tree in Python
    ... other nodes in the graph. ... Dijkstra code you are using it may be possible to help you with the ... finds shortest path between only two nodes. ... And what is the best way to represent a tree in Python?. ...
    (comp.lang.python)
  • Re: Graph optimization
    ... represented in the form of a graph. ... I have to add up all the weights to form the ... algorithm is going to be the best for finding the shortest path ...
    (comp.programming)
  • Re: Changing minimization to maximization, do the following problems change?
    ... if I know how to solve shortest path problem and then I ... you said this is NP-complete problem; ... Finding the longest path between two vertices in an acyclic graph ...
    (comp.theory)