如何处理通过Dijkstra算法遍历的图中的“组成节点”？

Question

我正在处理一个状态机，该状态机当前通过Dijkstra的算法遍历。但是，现在我需要增强该状态机，使其更“智能”地计算出解决某些副作用的途径。基本上，即使您处于该路径的正确起始状态，如果不满足某些要求，某些路径也是不可遍历的。通过首先遍历其他路径可以满足这些要求。我要解决的一个简化示例是在城市之间旅行：

• 您可以不带护照（仅提供基本身份证件）（例如，费城->纽约市）进行国内旅行
• 一旦您需要出国旅行，就需要护照（纽约市->巴黎）
• 如果您已经有护照，就可以出国旅行（纽约->巴黎）
• 如果您不这样做，则需要先回家带回家（纽约->费城->纽约->巴黎）

（我正在处理的另一个示例是网站状态以及登录和注销的概念）。

我正在考虑两种方法：

• 组成状态（即拥有护照本身是可以与“位置”状态结合在一起的第二状态），这听起来像会为我的状态机增加一个全新的维度，我不确定是否会构成该算法一团糟。
• 仅当处于状态时设置了某些属性时才有条件的路径（某种贝叶斯方法），这将有效地使我的状态“不纯”，其中转换将取决于内部状态属性，因此我更喜欢组合国家方法代替。

是否有一种干净的方法通过图论来表示这一点？是否有一般情况的算法可以处理能够穿越路径的这一初步要求？这个问题基本上是一个两阶段的Dijkstra搜索，您必须首先访问某个节点，但是如果您已经满足“拥有护照”的条件，则不需要访问该节点。

Answer 1

我发现this great answer是类似的问题。通过一些简化，可以将其应用于您的问题。

Answer 2