1
$\begingroup$

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!

$\endgroup$
2
  • $\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, 2017 at 5:55
  • $\begingroup$ Thanks for your answer. I don't know this algorithm, I will do a little research about it. $\endgroup$ Apr 10, 2017 at 8:52

1 Answer 1

0
$\begingroup$

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}$.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .