Shortest Path with Alternating Colors

Companies:
  • Amazon Interview Questions

Problem Statement

Consider a directed graph, with nodes labelled 0, 1, ..., n-1.  In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j.  Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

Return an array answer of length n, where each 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 such a path doesn’t exist).

Sample Test Case

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]
Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]
Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]
Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]
Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Problem Solution

The goal here is to find the shortest path between the source node to every other node in the graph with an additional condition that the path between any two nodes should be color alternating.

 We already know that we can find the shortest path between any two nodes in a graph using BFS.
The Brute force Idea could be to use BFS traversal n times so that we could find out the shortest path between all the nodes from the source node 0, But it will increase the Time Complexity. We can acheive this using a single BFS traversal.

First, we construct an adjacency matrix with the given red_edges and blue_edges.

It is important for us to keep in mind the fact that there can be at most two directed edges(in the same direction )between any two nodes(a blue edge and a red edge).

Here we can use a pair of int and int to keep track of the node index and the color of the edge respectively ( 0 for a red edge and 1 for a blue edge).

We can keep track of the three values in the queue, the first one to denote the node index, the second one for the distance and the third one for color (the color is -1 only for the source node).

Complexity Analysis

Time Complexity: O(n) since we are traversing through all the nodes only once.

Space Complexity:O(n) we are using queue to store the required values.

Code Implementation

#include<bits/stdc++.h>
using namespace std;

  void shortestAlternatingPaths(int n, vector<vector<int> >& red_edges, vector<vector<int> >& blue_edges) {
        vector<vector<pair<int,int> > > g(n);  //index, {neighbor index, color}
        for(auto& v:red_edges) g[v[0]].push_back({v[1], 0});
        for(auto& v:blue_edges) g[v[0]].push_back({v[1], 1});
        vector<vector<int> > vCost(n, vector<int>(2,-1));
        queue<pair<int,int> > q; // index, color(0 or 1)
        q.push({0,0});
        q.push({0,1});
        vCost[0] = {0,0};
        while(!q.empty()){
            auto [i, c1] = q.front(); q.pop();
            for(auto [j, c2] : g[i]){
                if(vCost[j][c2] != -1 || c1 == c2) continue;
                vCost[j][c2] = 1 + vCost[i][c1];
                q.push({j, c2});
            }
        }
        vector<int> res;
        for(auto& v : vCost) {
            sort(v.begin(), v.end());
            res.push_back(v[0] != -1 ? v[0] : v[1]);
        }
       for(int i=0;i<res.size();i++)
       {
           cout<<res[i]<<" ";
       }
    }

int main()
{   vector<int>temp;
    vector< vector<int> >red;
    temp.push_back(0); temp.push_back(1);
    red.push_back(temp);
    vector< vector<int> >blue;
    temp.clear();
    temp.push_back(2); temp.push_back(1);
    blue.push_back(temp);

    shortestAlternatingPaths(3,red,blue);
}

 

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]