Shortest Path with Alternating Colors

medium graph bfs shortest path

Problem

You are given a directed graph with n nodes labeled 0 to n−1. Edges come in two colors: red (redEdges) and blue (blueEdges). Return an array answer of length n where answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or −1 if no such path exists.

Inputn = 3, redEdges = [[0,1],[1,2]], blueEdges = []

Output[0, 1, -1]

Node 1 is reached via the red edge 0→1 (length 1). To leave node 1 we would need a blue edge, but none exists, so node 2 is unreachable.

n (nodes)

red edges (e.g. 0-1, 1-2)

blue edges (e.g. 1-2)

from collections import deque

def shortest_alternating_paths(n, red_edges, blue_edges):
    adj = [[[], []] for _ in range(n)]  # adj[u][color] -> neighbors
    for u, v in red_edges:
        adj[u][0].append(v)
    for u, v in blue_edges:
        adj[u][1].append(v)
    ans = [-1] * n
    seen = [[False, False] for _ in range(n)]
    q = deque([(0, 0), (0, 1)])          # start with either color allowed
    seen[0][0] = seen[0][1] = True
    dist = 0
    while q:
        for _ in range(len(q)):
            node, color = q.popleft()
            if ans[node] == -1:
                ans[node] = dist
            nxt = color ^ 1              # next edge must flip color
            for v in adj[node][nxt]:
                if not seen[v][nxt]:
                    seen[v][nxt] = True
                    q.append((v, nxt))
        dist += 1
    return ans

function shortestAlternatingPaths(n, redEdges, blueEdges) {
  const adj = Array.from({ length: n }, () => [[], []]);
  for (const [u, v] of redEdges) adj[u][0].push(v);
  for (const [u, v] of blueEdges) adj[u][1].push(v);
  const ans = new Array(n).fill(-1);
  const seen = Array.from({ length: n }, () => [false, false]);
  let q = [[0, 0], [0, 1]];
  seen[0][0] = seen[0][1] = true;
  let dist = 0;
  while (q.length) {
    const next = [];
    for (const [node, color] of q) {
      if (ans[node] === -1) ans[node] = dist;
      const nxt = color ^ 1;
      for (const v of adj[node][nxt]) {
        if (!seen[v][nxt]) { seen[v][nxt] = true; next.push([v, nxt]); }
      }
    }
    q = next;
    dist++;
  }
  return ans;
}

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[][] adj = new List[n][2];
        for (int i = 0; i < n; i++) { adj[i][0] = new ArrayList<>(); adj[i][1] = new ArrayList<>(); }
        for (int[] e : redEdges) adj[e[0]][0].add(e[1]);
        for (int[] e : blueEdges) adj[e[0]][1].add(e[1]);
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        boolean[][] seen = new boolean[n][2];
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0, 0}); q.add(new int[]{0, 1});
        seen[0][0] = seen[0][1] = true;
        int dist = 0;
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz > 0; sz--) {
                int[] cur = q.poll();
                int node = cur[0], color = cur[1];
                if (ans[node] == -1) ans[node] = dist;
                int nxt = color ^ 1;
                for (int v : adj[node][nxt]) {
                    if (!seen[v][nxt]) { seen[v][nxt] = true; q.add(new int[]{v, nxt}); }
                }
            }
            dist++;
        }
        return ans;
    }
}

vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
    vector<array<vector<int>, 2>> adj(n);
    for (auto& e : redEdges) adj[e[0]][0].push_back(e[1]);
    for (auto& e : blueEdges) adj[e[0]][1].push_back(e[1]);
    vector<int> ans(n, -1);
    vector<array<bool, 2>> seen(n, {false, false});
    queue<pair<int, int>> q;
    q.push({0, 0}); q.push({0, 1});
    seen[0][0] = seen[0][1] = true;
    int dist = 0;
    while (!q.empty()) {
        for (int sz = q.size(); sz > 0; sz--) {
            auto [node, color] = q.front(); q.pop();
            if (ans[node] == -1) ans[node] = dist;
            int nxt = color ^ 1;
            for (int v : adj[node][nxt]) {
                if (!seen[v][nxt]) { seen[v][nxt] = true; q.push({v, nxt}); }
            }
        }
        dist++;
    }
    return ans;
}

Explanation

We want shortest paths from node 0, but with a rule: edge colors must alternate red, blue, red, blue along the path. So the color of the edge you just used decides which edges you may take next. That makes the BFS state (node, color of last edge) instead of just node.

We store the graph split by color: adj[u][0] are red out-edges and adj[u][1] are blue. We start BFS from node 0 in both flavors — (0, red) and (0, blue) — because the first edge could be either color.

BFS proceeds level by level so distances come out in order. From a state with last color color, the next edge must flip color: nxt = color ^ 1. We follow only edges of color nxt, and we mark seen states as (node, color) so each node-color combo is visited once. The first time we reach a node, that level dist is its shortest answer.

Example: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []. We reach node 1 via red edge 0→1 at distance 1. To leave node 1 the next edge must be blue, but there are none, so node 2 is unreachable, giving [0, 1, -1].

Splitting each node into a red-arrival and blue-arrival state is the whole trick — it lets ordinary BFS respect the alternating constraint while still finding shortest distances.

Time: O(n + E) Space: O(n + E)