# Shortest Path with Alternating Colors

## 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)]

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

# 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()
if distance_b[q] is None:
queue_b.append(q)
distance_b[q] = distance_r[p] + 1
elif queue_b:
p = queue_b.popleft()
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

``````