Shortest Path with Alternating Colors — Editorial

Opening the reading…

Intuitionthe node alone does not contain enough information

An ordinary shortest-path search can describe its state with only the current node. Here that is not enough. Reaching node 4 after a red edge is different from reaching node 4 after a blue edge, because the next edge must have the opposite color. The same node can therefore need two separate distances.

Create a state for each pair of a node and the color of the edge used to reach it. From state (u, red), follow only blue edges; from state (u, blue), follow only red edges. Every edge has unit length, so BFS visits these states in nondecreasing path length and the first visit to a state is its shortest valid distance.

Node 0 has no previous edge, so its first edge may be either color. Starting both states at distance 0 represents that freedom: one state permits a blue first edge and the other permits a red first edge. At the end, a node may be reachable with either final color, so its answer is the smaller of the two state distances.

The BFS graph is the original graph expanded with the last-edge color.

ApproachBFS over node and last-color states

Store every directed edge as a pair of destination and color in one adjacency list, because the search must inspect both red and blue outgoing edges from each node.

Create dist[node][lastColor], initially -1, because two visits to the same node are not interchangeable when their last colors differ.

Set both states of node 0 to distance 0 and place both in the queue, because the first real edge is allowed to be red or blue even though no edge has preceded it.

Remove one state from the queue and inspect its outgoing edges, skipping an edge whose color equals lastColor, because taking it would break alternation.

For every allowed edge to v, visit the state dist[v][edgeColor] only if it is still -1, because BFS has already found the shortest route to every state that has been processed or queued.

Assign the new state distance as the current distance plus one and enqueue it, because traversing one directed edge increases the path length by exactly one.

For each node, take the minimum of its two state distances and leave the result at -1 when both are unreachable, because the final edge may have either color.

Complexitythe graph is expanded by only two states per node

MEASURE	BOUND	WHY
Time	O(n + m)	There are 2n possible states. Each state is settled at most once, and every adjacency entry is inspected when its source state is removed, so no edge entry is scanned more than twice for the two possible last colors.
Space	O(n + m)	The adjacency lists store m edge entries, while the distance table and queue store O(n) states. The returned answer has length n and is required output, so it is excluded from the extra-space bound. The bound is largest when the input contains all its allowed edge entries.

Here n is the number of nodes and m is the total number of red and blue directed edges.

Annotated solutionC++ · BFS on two states per node

CPPBuild the two-color state graph, run BFS, then combine the two distances for each node.

#include <algorithm>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> shortestAlternatingPaths(
        int n,
        vector<vector<int>>& redEdges,
        vector<vector<int>>& blueEdges
    ) {
        vector<vector<pair<int, int>>> adj(n);

        for (const auto& edge : redEdges) {
            adj[edge[0]].push_back({edge[1], 0});
        }
        for (const auto& edge : blueEdges) {
            adj[edge[0]].push_back({edge[1], 1});
        }

        vector<vector<int>> dist(n, vector<int>(2, -1));
        queue<pair<int, int>> q;

        dist[0][0] = 0;
        dist[0][1] = 0;
        q.push({0, 0});
        q.push({0, 1});

        while (!q.empty()) {
            auto [u, lastColor] = q.front();
            q.pop();

            for (auto [v, color] : adj[u]) {
                if (color == lastColor) {
                    continue;
                }
                if (dist[v][color] != -1) {
                    continue;
                }

                dist[v][color] = dist[u][lastColor] + 1;
                q.push({v, color});
            }
        }

        vector<int> answer(n, -1);
        for (int node = 0; node < n; ++node) {
            if (dist[node][0] != -1) {
                answer[node] = dist[node][0];
            }
            if (dist[node][1] != -1) {
                if (answer[node] == -1) {
                    answer[node] = dist[node][1];
                } else {
                    answer[node] = min(answer[node], dist[node][1]);
                }
            }
        }

        return answer;
    }
};

The key indexing choice is dist[v][color]. The color of the edge just taken becomes the last color for the next state, so the following iteration can reject edges with the same color. The condition dist[v][color] != -1 is also state-specific: reaching v after red does not mark reaching v after blue as visited.