Re: Shortest Path finding with mutating weights

From: Dennis Farr (dfarr_at_comcast.net)
Date: 11/01/04 

Date: 1 Nov 2004 13:37:15 -0800

If you can separate each edge weight into a constant positive minimum
and a nonnegative variable mutation min and max, I'm pretty sure
Dijkstra on the constant graph will help. The above restrictions may
be overly strong, I think you just need to make sure there are no
negative cycles. I do not see how your algorithm could decide to
remain stationary at a node unless you know the next weight in
advance. If this is so, you may be able to make multiple copies of the
graph and avoid the mutations entirely, and use plain old Dijkstra.

If you can compute a lower bound on the minimum path length between
any two nodes, for example if there is a distance metric between nodes
and the edge lengths never sum to less than the distance for any path,
then you may benefit by using the AStar variation of Dijkstra's
algorithm, especially if you do not need all the shortest paths from a
starting node.

Dennis Farr
Treefrog Enterprises