Shortest Path finding with mutating weights in a graph
Shortest Path finding with mutating weights
Dijkstra's algo can be used to find shortest path between 2 nodes in a weighted graph.
How to find shortest paths in a graph with mutating weights ?
Assume there is a formula to find weight of an edge (u, v)
w = f(u, v, t)
where t is the number of units of time.
It takes 1 unit of time to traverse a weight of "1". Assume there is also an edge from every node to itself with a weight "1". (ie For a better result we can wait in a node for many units of time instead of going to another node.)
(For example shortes path between node 0 and 5 can be
0->0->2->2->2->4->5
ie we wait in node 0 for 2 units, in node 2 for 3 units for a better results as weights are mutating over time.)
Assume that the amount of time that it takes to traverse an edge is locked in as soon as we start to traverse it.
(ie if we traverse an edge of weight 5. It takes 5 units of time. By this time, the weights of all edges would have changed including this edge as per above formula. But for traversing this edge we can assume the weight of this edge is locked to 5).
Does anyone know whether an algorithm exists for this ?
