# Shortest path between every pair of nodes in an /Or graph?

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!

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

## 1 Answer

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

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