Shortest Path with Alternating Colors

Problem Id: 1129 Difficulty: Medium Tag: Breadth-first Search Tag: Graph


Intuition

To get a shortest path from one node to another, we could use Breadth-first Search. But in this problem, there are 2 kinds of different edges, and edges color alternate along the path.

So, to solve this problem, we need to have 2 different bfs queue, and ofcourse, 2 different visited mark list.

Solution


from collections import deque


class DiGraph:
    def __init__(self, size):
        self.size = size
        self.adj = [[] for _ in range(size)]

    def add_edge(self, p, q):
        self.adj[p].append(q)


class Solution:
    def shortestAlternatingPaths(self, n, red_edges, blue_edges):
        # Build the graph
        graph_r = DiGraph(n)
        for p, q in red_edges:
            graph_r.add_edge(p, q)
        graph_b = DiGraph(n)
        for p, q in blue_edges:
            graph_b.add_edge(p, q)

        # Distance from edge of each color
        distance_r = [None] * n
        distance_b = [None] * n
        distance_r[0] = 0
        distance_b[0] = 0
        queue_r = deque([0])
        queue_b = deque([0])
        
        while True:
            if queue_r:
                p = queue_r.popleft()
                for q in graph_b.adj[p]:
                    if distance_b[q] is None:
                        queue_b.append(q)
                        distance_b[q] = distance_r[p] + 1
            elif queue_b:
                p = queue_b.popleft()
                for q in graph_r.adj[p]:
                    if distance_r[q] is None:
                        queue_r.append(q)
                        distance_r[q] = distance_b[p] + 1
            else:
                break
        
        ans = []
        for p in range(n):
            if distance_b[p] is None:
                ans.append(-1 if distance_r[p] is None else distance_r[p])
            elif distance_r[p] is None:
                ans.append(distance_b[p])
            else:
                ans.append(min(distance_b[p], distance_r[p]))
        return ans