Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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)?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.