Shortest Path with Alternating Colors

How it works

While BFS is typically preferred for shortest path problems, DFS can also work here because we are tracking distances and only updating when we find a shorter path. The recursion naturally handles the alternating color constraint. We start DFS from node 0 twice: once beginning with red edges and once with blue. Whenever we find a shorter path to a node with a particular ending color, we update the distance and continue exploring.

Steps

1. Build separate adjacency lists for red and blue edges.
2. Initialize a 2D distance array with infinity, setting dist[0][0] = dist[0][1] = 0.
3. Run DFS starting from node 0 with color 0 (red), then again with color 1 (blue).
4. In DFS for state (node, color):
   • For each neighbor reachable via the current color:
     • If dist[neighbor][opposite_color] > dist[node][color] + 1:
       • Update the distance.
       • Recursively call DFS on the neighbor with the opposite color.
5. Build the answer by taking the minimum of both color distances for each node.
6. Return -1 for unreachable nodes.

Complexity

• Time complexity: O(V + E)
• Space complexity: O(V + E)

Where V is the number of vertices and E is the number of edges.

Things to watch for

Tracking Only Node Visits Instead of (Node, Color) Pairs

A common mistake is marking nodes as visited based solely on the node ID, ignoring the color of the edge used to reach it. Since reaching node X via a red edge allows different future moves than reaching it via a blue edge, you must track visited states as (node, last_edge_color) pairs. Without this, you may prematurely block valid paths that use a different edge color.

Forgetting to Allow Both Starting Colors

Since there is no edge leading into node 0, both red and blue edges are valid first moves. Failing to initialize the BFS with both color options (or using a sentinel value like None or -1 for "no previous color") means you might miss the shortest path if it requires starting with a specific color.

Not Recording Distance on First Visit

In BFS for shortest paths, the first time you reach a node is guaranteed to be via the shortest path. A pitfall is updating the answer every time a node is encountered rather than only on the first visit. This can lead to incorrect results if you overwrite an earlier (shorter) distance with a later (longer) one when the node is reached through a different color sequence.

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: list[list[int]], blueEdges: list[list[int]]) -> list[int]:
        def buildGraph(edges):
            adj = [[] for _ in range(n)]
            for u, v in edges:
                adj[u].append(v)
            return adj

        red, blue = buildGraph(redEdges), buildGraph(blueEdges)
        adj = [red, blue]
        INF = float("inf")
        dist = [[INF] * 2 for _ in range(n)]
        dist[0][0] = dist[0][1] = 0

        def dfs(node, color):
            for nei in adj[color][node]:
                if dist[nei][color ^ 1] > dist[node][color] + 1:
                    dist[nei][color ^ 1] = dist[node][color] + 1
                    dfs(nei, color ^ 1)

        dfs(0, 0)
        dfs(0, 1)

        answer = [0] + [-1] * (n - 1)
        for i in range(1, n):
            answer[i] = min(dist[i][0], dist[i][1])
            if answer[i] == INF:
                answer[i] = -1

        return answer

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<int>> adj[2] = {buildGraph(n, redEdges), buildGraph(n, blueEdges)};

        int INF = numeric_limits<int>::max();
        vector<vector<int>> dist(n, vector<int>(2, INF));
        dist[0][0] = dist[0][1] = 0;

        dfs(0, 0, adj, dist);
        dfs(0, 1, adj, dist);

        vector<int> answer(n, -1);
        for (int i = 0; i < n; i++) {
            answer[i] = min(dist[i][0], dist[i][1]);
            if (answer[i] == INF) answer[i] = -1;
        }
        return answer;
    }

private:
    void dfs(int node, int color, vector<vector<int>> adj[], vector<vector<int>>& dist) {
        for (int nei : adj[color][node]) {
            if (dist[nei][color ^ 1] > dist[node][color] + 1) {
                dist[nei][color ^ 1] = dist[node][color] + 1;
                dfs(nei, color ^ 1, adj, dist);
            }
        }
    }

    vector<vector<int>> buildGraph(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
        }
        return adj;
    }
};