给定3种颜色顶点的图形，找到具有以下条件的最短路径

Question

给定无向图G，其中每个顶点用绿色红色或蓝色和正权重着色，找到以节点T结尾的最短路径，具有以下条件：

1.只有当我越过路径中的红色顶点时才能使用绿色顶点。

2.只有当我经过红色的顶点和路径中的绿色顶点时，才能使用蓝色顶点。

我尝试使用DFS并找到可能的路径，然后在可能的路径中从节点T启动Dijkstra算法，但复杂性太高。谢谢！

Answer 1

Dijkstra是寻找最短路径的好方法。在您的情况下，您还必须注意路径上的第一个顶点必须是红色，并且只有在访问绿色顶点时才能使用蓝色顶点。 解决方案可以是以下（在pythonic伪代码中）：

def red__and_green_dijkstra(G, origin, dest):
    for node in G.nodes():
        node.was_visited_R = False
        node.was_visited_RG = False
    origin.was_visited_R = True
    origin.was_visited_RG = True
    Q = empty_priority_queue()
    for neighbor in origin.neighbors():
        if neighbor.color == red:
            Q.push((weight(origin, neighbor), neighbor, [origin, neighbor], False))
        if neighbor.color == green and origin.color == red:
            Q.push((weight(origin, neighbor), neighbor, [origin, neighbor], True))
    while not Q.is_empty():
        dist, node, path, can_pick_blue = Q.pop()
        node.was_visited_R = True  # mark the node as visited with a 'red' path
        if can_pick_blue:
            node.was_visited_RG = True  # mark the node as visited on a 'red and green' path
        if node == dest:
            return path
        for neighbor in node.neighbors():
            if can_pick_blue:  # met at least 1 green node on path so far
                if neighbor.color == red and not neighbor.was_visited_RG:
                    Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], True))
                if neighbor.color == green and not neighbor.was_visited_RG:
                    Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], True))
                if neighbor.color == blue and not neighbor.was_visited_RG:
                    Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], True))
            else:  # only red nodes on path so far
                if neighbor.color == red and not neighbor.was_visited_RG:
                    Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], False))
                if neighbor.color == green and not neighbor.was_visited_RG:
                    Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], True))

1. 到原点的距离：我们还使用它作为队列中给出优先级的值（我们pop()具有最低距离的节点）
2. 当前节点
3. 整个路径：由于您需要路径（而不仅仅是距离），您还需要将其存储在队列中
4. 布尔can_pick_blue。由于队列是用红色节点初始化的，我们确信我们可以选择一个绿色节点。但对于蓝色节点，我们需要确保路径中至少有一个绿色节点和一个红色节点。此布尔值会跟踪此信息。可以检查路径中的所有节点，但这样做会更昂贵。

对于初始化，我们需要区分2种情况：

• 如果原点是红色，我们可以开始使用红色和绿色节点，因为路径中已经有一个红色节点。
• 如果原点不是红色，那么我们必须选择一个红色节点。

稍后，当我们在主循环中循环节点的邻居时，我们需要查看是否可以在队列中推送此邻居。所以我们需要检查它是否已经被访问过，并且在它是蓝色的情况下，我们需要确保当前节点的can_pick_blue值实际为真。

该算法的复杂性与Dijkstra的O(n.log n)相同。

编辑：为了得到正确的结果，我添加了第二个布尔值来将节点标记为已访问。实际上，您需要其中两个：一个是知道节点是否已在“仅红色”路径上访问，其中禁止选择蓝色，另一个知道节点是否已在“红色和绿色”上访问（并最终蓝色路径，也可以选择蓝色节点。 实际上，它需要能够选择所有相关路径，并丢弃冗余路径。