Shortest Path with Alternating Colors

class Solution {
public:
    vector<int> findShortestAlternatingPaths(int n, vector<vector<int>>& edgesRed,
                                             vector<vector<int>>& edgesBlue) {
        vector<vector<pair<int, int>>> graph(n);
        for (auto& edge : edgesRed) {
            graph[edge[0]].emplace_back(edge[1], 0);
        }
        for (auto& edge : edgesBlue) {
            graph[edge[0]].emplace_back(edge[1], 1);
        }

        vector<int> distances(n, -1);
        vector<vector<bool>> visited(n, vector<bool>(2));
        queue<vector<int>> nodesQueue;

        // Initialize with the starting node 0, step count 0, and no previous color
        nodesQueue.push({0, 0, -1});
        visited[0][0] = visited[0][1] = true;
        distances[0] = 0;

        while (!nodesQueue.empty()) {
            auto current = nodesQueue.front();
            int currentNode = current[0], currentSteps = current[1], lastColor = current[2];
            nodesQueue.pop();

            for (auto& [nextNode, edgeColor] : graph[currentNode]) {
                if (!visited[nextNode][edgeColor] && edgeColor != lastColor) {
                    visited[nextNode][edgeColor] = true;
                    nodesQueue.push({nextNode, currentSteps + 1, edgeColor});
                    if (distances[nextNode] == -1) distances[nextNode] = currentSteps + 1;
                }
            }
        }
        return distances;
    }
};

The provided solution aims to find the shortest paths from an initial node to all other nodes in a graph with edges that alternate in two colors. This specific task requires simulating navigating a graph where each step to a connected node must alternate from the previous color used.

• In the given C++ program:

  • A graph is constructed in which each node maintains a list of pairs, representing connections to other nodes and whether the edge is red (0) or blue (1).
  • Breadth-First Search (BFS) is used to explore paths from the start node (node 0). A queue is utilized to keep track of the nodes as the search progresses, keeping an account of the node index, the number of steps taken from the start, and the color of the last edge used.
  • The program begins by marking the starting node and queuing it with initial values including 0 steps and an indicator that no color has been used (-1).
  • Numeric limits are initiated with the distance to each node from the start initially set to -1, and marking unvisited for both color edges on all nodes.
  • Throughout the BFS, for each node, all possible next steps are examined. If the next node's corresponding color pathway hasn't been visited and the edge color is not the same as the last, the node is marked as visited for that color. It's then pushed onto the queue with updated step count and color details.
  • If a shorter path to a node is found, that node's distance is updated.

• Important operations and checks include:

  • Alternating the color of the edges accessed on consecutive steps,
  • Utilizing BFS for level-wise exploration ensuring the shortest path calculation,
  • Keeping track of both edge colors for each node to ensure color alternation conditions are met without revisiting in the same BFS layer.

This technique is efficient in scenarios where constraints on path selection in terms of attributes like edge color are in place, ensuring that each connection not only leads to a possible path but also adheres to the alternation rule. The solution effectively calculates the shortest alternating path lengths from a single starting node to every other node in the given graph setup.

class Solution {
    public int[] findShortestAlternatingPaths(int n, int[][] red, int[][] blue) {
        Map<Integer, List<List<Integer>>> graph = new HashMap<>();
        for (int[] redEdge : red) {
            graph.computeIfAbsent(redEdge[0], x -> new ArrayList<>()).add(Arrays.asList(redEdge[1], 0));
        }

        for (int[] blueEdge : blue) {
            graph.computeIfAbsent(blueEdge[0], x -> new ArrayList<>()).add(Arrays.asList(blueEdge[1], 1));
        }

        int[] results = new int[n];
        Arrays.fill(results, -1);
        boolean[][] seen = new boolean[n][2];
        Queue<int[]> queue = new LinkedList<>();

        queue.offer(new int[] {0, 0, -1}); // Starting node with 0 distance and undefined last color
        results[0] = 0;
        seen[0][0] = seen[0][1] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentNode = current[0], currentDist = current[1], lastColor = current[2];

            if (!graph.containsKey(currentNode)) {
                continue;
            }

            for (List<Integer> adjNode : graph.get(currentNode)) {
                int nextNode = adjNode.get(0);
                int edgeColor = adjNode.get(1);
                if (!seen[nextNode][edgeColor] && edgeColor != lastColor) {
                    if (results[nextNode] == -1)
                        results[nextNode] = currentDist + 1;
                    seen[nextNode][edgeColor] = true;
                    queue.offer(new int[] {nextNode, currentDist + 1, edgeColor});
                }
            }
        }
        return results;
    }
}

This Java program solves the problem of finding the shortest alternating paths from a starting node to all other nodes in a graph with two types of edges (represented by colors red and blue). The graph is represented in a way that each node can have outgoing edges differentiated by colors.

Follow these major steps within the code:

1. Create a graph representation using a HashMap to store adjacency lists, differentiated by edge color. Each node in the graph points to separate lists for red (0) and blue (1) edges.

2. Initialize a results array to store the shortest path lengths for each node. Set all initially to -1 and mark only the starting node 0 as 0 indicating no distance from the start.

3. Use a two-dimensional boolean array to keep track of visited states. This ensures that the same node isn't revisited via the same colored edge.

4. Utilize a queue mechanism for breadth-first search (BFS). The queue elements hold the current node's index, the distance traveled to reach this node, and the last edge's color used to reach this node.

5. Process each node by examining its adjacency list. Add neighboring nodes to the queue only if they haven't been reached by the same colored edge previously, and if the last edge color used differs from the current edge's color. This effectively manages the alternating color requirement.

6. For each eligible neighboring node, if it hasn't been reached before (results[nextNode] == -1), update its shortest distance. Then, mark it as seen and enqueue it for further examination.

7. The BFS continues until the queue is empty, ensuring all possible paths are explored.

Finally, return the results array which now contains the shortest distances for all nodes from the start node with color alternating constraints.

This approach ensures a thorough search of potential paths while respecting the constraints set by the alternating colored edges, leveraging BFS for an effective implementation.