Pathfinding

[imcram]

Hi,
Can anyone tell me how to find the shortest path in a graph when the weights of the graph are dynamic? That is if u go from A to B, the weight of B to C will change in some deterministic way. Can anyone at least point me to some resources? Because I have raised the same question before and I did not get a satisfactory answer from anyone. Thank you.

[RedSon]

Hi,
Can anyone tell me how to find the shortest path in a graph when the weights of the graph are dynamic? That is if u go from A to B, the weight of B to C will change in some deterministic way. Can anyone at least point me to some resources? Because I have raised the same question before and I did not get a satisfactory answer from anyone. Thank you.

Hmm graph theory is a tough subject. What are you trying to accomplish? Finding a good algorithm is going to be difficult. Some common ways to approach shortest path is to use greedy algorithms, or Dijkstra. You can check out Wikipedia for Shortest Path Problems or this site for Dijkstra's.

[imcram]

I am able to use Dijkstra's or other conventional pathfinders. This is the problem with them:

Usually the weights of the edges of the graph are static. They are not affected by the path taken. But, what if the weights themselves are affected by the path taken so far? Ex:

Think of school transport. There is a bus that transports students to the school. Let us say that the fuel cost per unit distance is proportional to the students onboard. There are children in different places, and all of them have to get to the school. Suppose we want to find out the path which would collect all the children and deleiver them to the school while minimizing the fuel cost. How do we do this? I can't think of an algorithm for such a problem. If anyone can help, I'd be most glad.

[RedSon]

It is the same problem you just have to do pathfinding at each node. Every time you get to a node you again have to see which is the shortest path. I assume that once you choose a path the weight of the path from the node you are in to the next node will not change. If it changes while you are on the path then there is no way to find the shortest path from one node to another.