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