Re: Time Dependent Shortest Path


chenyan wrote:
|What's the best known algorithm for time dependent shortest path
|problems?
|The difference compared to normal shortest path problem is the weight
|of each edge can be dynamically changing according to time.

I'm sure the best algorithm depends on details that aren't
explicit here, but a lot of these problems can be reduced
to time independent shortest path by treating nodes at
different times as if they are different nodes.

Keith Ramsay

.

Relevant Pages

  • Re: Graph Algorithm Question
    ... is there an algorithm to do the following: ... However the graph should contain no directed ... cycle whose weight is negative. ... If all the edges weighs are positive then shortest path from X to X is ...
    (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: which algorithm fits...
    ... >> for example, the 60th shortest path, that makes finding the right path ... >The most important thing that is still not known is how much memory you can ... >you can either do a depth first search, ... the algorithm appears to need some way to ...
    (comp.programming)
  • Re: Shortish paths
    ... Remember I'm not asking for an algorithm, just for advice on what to ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • 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)