shortest path with dynamic edge cost (algorithm)

I'm looking for an algorithm that can find the shortest path between two nodes in an undirected graph with a cost which is dynamic. By dynamic, I mean that the cost on edge is dependent on the next (future) step. For example, in a graph like that:

I'm looking for the shortest path from "a" to "e" but the cost of "a" to "b" depends on next step. If I go to c, it is 7, and if I go to d, it is 9.

My question is: Is there an algorithm which solves that problem?

---

Reduce the problem to 'regular' shortest path problem

Create dummy vertices b1,b2 (instead of b ), and the edges:

(a,b1,7), (b1,c,6), (a,b2,9), (b2,d,5)

The rest of the edges and vertices remain as they originally were.

Now, run regular shortest path algorithm (Dijkstra / Bellman Ford) from the source to the target.

(Repeat the process for any 'conditional' weight edges).

---

As mentioned by a previous answer, since the edge weight only depends on the next vertex in the path you can duplicate each vertex with at most |V| duplicates that keeps track of which vertex is traveled next, where each duplicate vertex only has only one outgoing neighbor and the outgoing cost depends on which neighbor is visited next. The total complexity of running Dijkstra's algorithm on this modified graph is no worse than O(V(V log v + E)), and if you have bounded edge degree k at each vertex then the complexity is O(k(V log V + E)), where V is the number of vertices and E is the number of edges.

链接地址: http://www.djcxy.com/p/35220.html

上一篇: 图表和PRIM和DIJKSTRA问题？

下一篇: 具有动态边缘成本的最短路径（算法）