⚡Flashcard Drill➔
NeetCode #587LC-1129MediumGraphs
← Back to All Problems

#587 · #1129 · Shortest Path with Alternating Colors(颜色交替的最短路径)

📌 Problem Statement & Constraints

You are given a directed graph with red edges and blue edges. Return the shortest path length from node 0 to each node such that the edge colours alternate; return -1 for unreachable nodes. Constraints: 1 <= n <= 100, 0 <= redEdges.length, blueEdges.length <= 400.

💡 Core Algorithmic Approaches

  1. The state is (node, colour of the last edge used), since the next edge must be the opposite colour.
  2. So BFS over 2n states rather than n nodes.
  3. Start with both colours at distance 0 from node 0 (no edge has been used yet).
  4. The answer per node is the minimum of its two state distances, or -1 if both are unreachable.

💻 Benchmark Python3 Implementation

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        from collections import defaultdict, deque
        g = [defaultdict(list), defaultdict(list)]   # 0 = red, 1 = blue
        for a, b in redEdges:
            g[0][a].append(b)
        for a, b in blueEdges:
            g[1][a].append(b)

        dist = [[-1, -1] for _ in range(n)]   # dist[node][last colour]
        dist[0][0] = dist[0][1] = 0
        q = deque([(0, 0), (0, 1)])
        while q:
            node, col = q.popleft()
            for nxt in g[1 - col][node]:      # must use the opposite colour
                if dist[nxt][1 - col] == -1:
                    dist[nxt][1 - col] = dist[node][col] + 1
                    q.append((nxt, 1 - col))

        res = []
        for d in dist:
            cands = [x for x in d if x != -1]
            res.append(min(cands) if cands else -1)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O((V + E) * 2): each state is visited once.
💾 Space Complexity
O(V * 2) for the distance table plus the graph.

⚠️ Interview Pitfalls & Follow-ups

  • Tracking only the node: the alternation constraint requires the last edge's colour in the state.
  • Starting with only one colour: both are valid starting states.
  • Using the same colour for the next edge: the transition must use 1 - col.
  • Returning the first colour's distance: the minimum over both states is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems