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