I am dealing with directed graphs that consist of two types of (uniquely non-negative weighted) node, "OR" nodes and "AND" nodes. Given a single source and a single target, I want to find the shortest path (with minimal weight) between them.
"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.
Now, when trying to find the shortest path to an "AND" node, simply summing up the node's parents' weight won't work, since they might have ancestors in common, which would lead to the ancestors' weight being accounted for several times.
Does anybody know of an algorithm that would solve this? And if yes, what would be its complexity? I have not been able to find much in the literature. I probably am not using the right terminology. Or?
Thanks a lot!