# How to find optimal path visit every node with parallel workers complicated by dynamic edge costs?

Say you have an acyclic directed graph with weighted edges and create N workers.

My goal is to calculate the optimal way those workers can traverse the entire graph in parralel.

However, edge costs may change along the way.

Example:

``````A -1-> B
A -2-> C
B -3-> C (if A has already been visited)
B -5-> C (if A has not already been visited)
``````

Does what I describe lend itself to a standard algorithmic approach, or alternately can someone suggest if I'm looking at this in an inherently flawed way (i have an intuition I might be)?

-
You can turn it into a single-worker problem by defining a new graph with a node for every possible configuration of the original graph and edges for allowed transitions between states of the original graph. This way you also get static costs. – Patrick Oct 25 '12 at 22:15
IIRC, A*, with a node that is not connected to the graph will produce what you want (it flood fills optimally). There's an article in AI Game Programming Wisdom 3 (or 2, I forget). Not sure what you mean by N workers though... are those N workers in the graph, and are they allowed to collide? occupy the same nodes? What are the constraints on the workers? Or by workers, do you mean worker threads? It's been a while, but I recall that pathfinding is terribly difficult to parallelize. – Steve Evers Oct 25 '12 at 22:45