具有所需顶点的有向加权图
Directed Weighted Graph with required vertices
给定：一个有向加权图G=(V, E)，一些顶点是红色的，一些是蓝色的，其余的是白色的，权重Ti是允许从任何顶点到红色顶点的最大权重到任何蓝色顶点。
问题：创建一个算法，找到一条从源节点 S 到目标节点 T 的路径，权重最小，并且在到达顶点 T 之前从红色顶点到蓝色顶点的权重最大为 Ti。该算法的时间复杂度应为 O(n^3)
评论：我不确定如何开始这个，我认为这是 Dijkstra 算法的一些变体，我看到一些人谈论制作图表的副本并连接副本，但除此之外，我我不确定这个算法的设置是什么样的。任何帮助将不胜感激。
的确，您可以使用如下复制策略：
复制图G到G'和G。标记所有顶点在 G' 中与在 G 中一样，但带有撇号。所以有一个 S' 和一个T' in G'。类似地，S" 和 T"属于G.
设S为起始顶点，T为目标点。就目前而言，G 、G'和G断开连接。但是添加以下零权重，有向边：
- 从G中的每个红色顶点r到它在r'中的镜像的边G'.
- 从 G' 中的每个蓝色顶点 b' 到其镜像 b 的边] 在 G.
因此没有从 G" 到 G' 的路径，也不存在从 G' 的路径] 到 G，也不从 G" 到 G.
现在开始S中的Dijkstra算法，优先级队列中的每个条目都有一个额外的数据属性：中边累积的路径权重G'仅。我们称之为 w'。这个w'对队列的优先级没有任何作用。一条路径的 总 权重决定优先级，这是 Dijkstra 算法的标准。该算法不应扩展 w' 超过 Ti 的路径。除了该特定限制之外，该算法的所有其余部分都可以保留为标准 Dijkstra 算法。
给定：一个有向加权图G=(V, E)，一些顶点是红色的，一些是蓝色的，其余的是白色的，权重Ti是允许从任何顶点到红色顶点的最大权重到任何蓝色顶点。
问题：创建一个算法，找到一条从源节点 S 到目标节点 T 的路径，权重最小，并且在到达顶点 T 之前从红色顶点到蓝色顶点的权重最大为 Ti。该算法的时间复杂度应为 O(n^3)
评论：我不确定如何开始这个，我认为这是 Dijkstra 算法的一些变体，我看到一些人谈论制作图表的副本并连接副本，但除此之外，我我不确定这个算法的设置是什么样的。任何帮助将不胜感激。
的确，您可以使用如下复制策略：
复制图G到G'和G。标记所有顶点在 G' 中与在 G 中一样，但带有撇号。所以有一个 S' 和一个T' in G'。类似地，S" 和 T"属于G.
设S为起始顶点，T为目标点。就目前而言，G 、G'和G断开连接。但是添加以下零权重，有向边：
- 从G中的每个红色顶点r到它在r'中的镜像的边G'.
- 从 G' 中的每个蓝色顶点 b' 到其镜像 b 的边] 在 G.
因此没有从 G" 到 G' 的路径，也不存在从 G' 的路径] 到 G，也不从 G" 到 G.
现在开始S中的Dijkstra算法，优先级队列中的每个条目都有一个额外的数据属性：中边累积的路径权重G'仅。我们称之为 w'。这个w'对队列的优先级没有任何作用。一条路径的 总 权重决定优先级，这是 Dijkstra 算法的标准。该算法不应扩展 w' 超过 Ti 的路径。除了该特定限制之外，该算法的所有其余部分都可以保留为标准 Dijkstra 算法。