I am dealing with a weighted directed graphs(uniquely non-negative weighted) that consist of two types of node, "OR" nodes and "AND" nodes. I want to find the shortest path (with minimal weight) between every pair of vertices

"OR" nodes are regular nodes: they can be visited if at least one of their parents has been visited first. "AND" nodes have a constraint: all their parents must have been visited first.

Could we use (After some changement ...) Floyd or Dijkstra to calculate the shortest path between every pair of nodes?

Thanks a lot!

  • $\begingroup$ I think this problem instance is similar to game tree evaluation. There is a good randomized algorithm for this problem $\endgroup$ – YOUSEFY Apr 9 '17 at 5:55
  • $\begingroup$ Thanks for your answer. I don't know this algorithm, I will do a little research about it. $\endgroup$ – hajar elmaghraoui Apr 10 '17 at 8:52

The Travelling Salesman problem can be polynomially reduced to your problem, therefore this problem is NP-hard and has no polynomial solution if $\mathrm P \ne \mathrm{NP}$.

  • $\begingroup$ and what about AO* $\endgroup$ – hajar elmaghraoui Apr 13 '17 at 18:29
  • $\begingroup$ What do you mean? $\endgroup$ – Smylic Apr 14 '17 at 11:09
  • $\begingroup$ By searching the net, I found that the algorithm AO * calculates the shortest path in an AND/OR graph. $\endgroup$ – hajar elmaghraoui Apr 15 '17 at 18:13
  • $\begingroup$ Is it polynomial? $\endgroup$ – Smylic Apr 15 '17 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.