Shortest path for a thief to reach the Nth house avoiding policemen - Coding

Given an unweighted graph and a boolean array A[ ], where if the i^th index of array A[ ] denotes if that node can be visited (0) or not (1). The task is to find the shortest path to reach (N – 1)^th node from the 0^th node. If it is not possible to reach, print -1.

Examples :

Input : N = 5, A[] = {0, 1, 0, 0, 0}, Edges = {{0, 1}, {0, 2}, {1, 4}, {2, 3}, {3, 4}}
Output: 3
Explanation: There are two paths from 0^th house to 4^th house

0 ? 1 ? 4

0 ?2 ? 3 ? 4

Since a policeman is present at the 1^st house, the only path that can be chosen is the 2nd path.

Input : N = 4, A[] = {0, 1, 1, 0}, Edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}}
Output : -1

Approach: This problem is similar to finding the shortest path in an unweighted graph. Therefore, the problem can be solved using BFS.

Follow the steps below to solve the problem:

Initialize an unordered_map, say adj to store the edges. The edge (a, b) must be excluded if there is a policeman either at node a or at node b.
Initialize a variable, pathLength = 0.
Initialize a vector of the boolean data type, say visited, to store whether a node is visited or not.
Initialize an arraydist[0, 1, …., v-1] such that dist[i] stores the distance of vertex i from the root vertex
Initialize a queue and push node 0 in it. Also, mark node 0 as visited.
Iterate while the queue is not empty and the node N – 1 is not visited, pop the front element from the queue, and push all the elements into the queue that have an edge from the front element of the queue and are not visited and increase the distance of all these nodes by 1 + dist[q.top()].
If the node (N – 1) is not visited, then print -1.
Otherwise, print the distance of (N – 1)^th node from the root node.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to create graph edges
// where node A and B can be visited
void createGraph(unordered_map<int, vector<int> >& adj,
                 int paths[][2], int A[], int N, int E)
{
    // Visit all the connections
    for (int i = 0; i < E; i++) {
 
        // If a policeman is at any point of
        // connection, leave that connection.
        // Insert the connect otherwise.
        if (!A[paths[i][0]] && !A[paths[i][1]]) {
 
            adj[paths[i][0]].push_back(paths[i][1]);
        }
    }
}
 
// Function to find the shortest path
int minPath(int paths[][2], int A[],
            int N, int E)
{
    // If police is at either at
    // the 1-st house or at N-th house
    if (A[0] == 1 || A[N - 1] == 1)
 
        // The thief cannot reach
        // the N-th house
        return -1;
 
    // Stores Edges of graph
    unordered_map<int, vector<int> > adj;
 
    // Function call to store connections
    createGraph(adj, paths, A, N, E);
 
    // Stores whether node is
    // visited or not
    vector<int> visited(N, 0);
 
    // Stores distances
    // from the root node
    int dist[N];
    dist[0] = 0;
 
    queue<int> q;
    q.push(0);
    visited[0] = 1;
 
    // Visit all nodes that are
    // currently in the queue
    while (!q.empty()) {
 
        int temp = q.front();
        q.pop();
 
        for (auto x : adj[temp]) {
 
            // If current node is
            // not visited already
            if (!visited[x]) {
 
                q.push(x);
                visited[x] = 1;
                dist[x] = dist[temp] + 1;
            }
        }
    }
 
    if (!visited[N - 1])
        return -1;
    else
        return dist[N - 1];
}
 
// Driver Code
int main()
{
    // N : Number of houses
    // E: Number of edges
    int N = 5, E = 5;
 
    // Given positions
    int A[] = { 0, 1, 0, 0, 0 };
 
    // Given Paths
    int paths[][2] = { { 0, 1 },
                       { 0, 2 },
                       { 1, 4 },
                       { 2, 3 },
                       { 3, 4 } };
 
    // Function call
    cout << minPath(paths, A, N, E);
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class GFG {
 
    // Function to create graph edges
    // where node A and B can be visited
    static void
    createGraph(HashMap<Integer, ArrayList<Integer> > adj,
                int paths[][], int A[], int N, int E)
    {
        // Visit all the connections
        for (int i = 0; i < E; i++) {
 
            // If a policeman is at any point of
            // connection, leave that connection.
            // Insert the connect otherwise.
            if (A[paths[i][0]] != 1
                && A[paths[i][1]] != 1) {
                ArrayList<Integer> list = adj.getOrDefault(
                    paths[i][0], new ArrayList<>());
                list.add(paths[i][1]);
                adj.put(paths[i][0], list);
            }
        }
    }
 
    // Function to find the shortest path
    static int minPath(int paths[][], int A[], int N, int E)
    {
        // If police is at either at
        // the 1-st house or at N-th house
        if (A[0] == 1 || A[N - 1] == 1)
 
            // The thief cannot reach
            // the N-th house
            return -1;
 
        // Stores Edges of graph
        HashMap<Integer, ArrayList<Integer> > adj
            = new HashMap<>();
 
        // Function call to store connections
        createGraph(adj, paths, A, N, E);
 
        // Stores whether node is
        // visited or not
        boolean visited[] = new boolean[N];
 
        // Stores distances
        // from the root node
        int dist[] = new int[N];
        dist[0] = 0;
 
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.addLast(0);
        visited[0] = true;
 
        // Visit all nodes that are
        // currently in the queue
        while (!q.isEmpty()) {
 
            int temp = q.removeFirst();
 
            for (int x : adj.getOrDefault(
                     temp, new ArrayList<>())) {
 
                // If current node is
                // not visited already
                if (!visited[x]) {
 
                    q.addLast(x);
                    visited[x] = true;
                    dist[x] = dist[temp] + 1;
                }
            }
        }
 
        if (!visited[N - 1])
            return -1;
        else
            return dist[N - 1];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // N : Number of houses
        // E: Number of edges
        int N = 5, E = 5;
 
        // Given positions
        int A[] = { 0, 1, 0, 0, 0 };
 
        // Given Paths
        int paths[][] = {
            { 0, 1 }, { 0, 2 }, { 1, 4 }, { 2, 3 }, { 3, 4 }
        };
 
        // Function call
        System.out.print(minPath(paths, A, N, E));
    }
}
 
// This code is contributed by Kingash.

Python3

# Python program for the above approach
 
# Stores Edges of graph
 
adj = {};
 
# Function to create graph edges
# where node A and B can be visited
def createGraph(paths, A, N, E):
    # Visit all the connections
    for i in range(E):
 
        # If a policeman is at any point of
        # connection, leave that connection.
        # Insert the connect otherwise.
        if (not A[paths[i][0]] and not A[paths[i][1]]) :
 
            if(paths[i][0] in adj):
                tmp = adj[paths[i][0]];
                tmp.append(paths[i][1]);
                adj[paths[i][0]] = tmp;
             
            else:
             
                tmp = [];
                tmp.append(paths[i][1]);
                adj[paths[i][0]] = tmp;
 
# Function to find the shortest path
def minPath(paths, A, N, E):
    # If police is at either at
    # the 1-st house or at N-th house
    if (A[0] == 1 or A[N - 1] == 1):
 
        # The thief cannot reach
        # the N-th house
        return -1;
 
    # Function call to store connections
    createGraph(paths, A, N, E);
 
    # Stores whether node is
    # visited or not
    visited = [0] * N
 
    # Stores distances
    # from the root node
    dist = [0] * N
    dist[0] = 0;
 
    q = [];
    q.append(0);
    visited[0] = 1;
 
    # Visit all nodes that are
    # currently in the queue
    while (len(q) != 0):
 
        temp = q[0];
        q.pop();
 
        if(temp in adj):
            for x in adj[temp] :
 
                # If current node is
                # not visited already
                if (not visited[x]):
 
                    q.append(x);
                    visited[x] = 1;
                    dist[x] = dist[temp] + 1;
                 
 
    if (not visited[N - 1]):
        return -1;
    else:
        return dist[N - 1];
 
 
# Driver Code
# N : Number of houses
# E: Number of edges
N = 5
E = 5;
 
# Given positions
A = [0, 1, 0, 0, 0 ];
 
# Given Paths
paths = [ [ 0, 1 ],
                   [ 0, 2 ],
                   [ 1, 4 ],
                   [ 2, 3 ],
                   [ 3, 4 ] ];
# Function call
print(minPath(paths, A, N, E));
 
# This code is contributed by Saurabh Jaiswal

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace GFG {
  class Program {
    static void Main(string[] args)
    {
      // N : Number of houses
      // E: Number of edges
      int N = 5, E = 5;
 
      // Given positions
      int[] A = { 0, 1, 0, 0, 0 };
 
      // Given Paths
      int[][] paths
        = { new int[] { 0, 1 }, new int[] { 0, 2 },
           new int[] { 1, 4 }, new int[] { 2, 3 },
           new int[] { 3, 4 } };
 
      // Function call
      Console.WriteLine(MinPath(paths, A, N, E));
    }
 
    // Function to create graph edges
    // where node A and B can be visited
    static void CreateGraph(Dictionary<int, List<int> > adj,
                            int[][] paths, int[] A, int N,
                            int E)
    {
      // Visit all the connections
      for (int i = 0; i < E; i++) {
        // If a policeman is at any point of
        // connection, leave that connection.
        // Insert the connect otherwise.
        if (A[paths[i][0]] != 1
            && A[paths[i][1]] != 1) {
          List<int> list
            = adj.ContainsKey(paths[i][0])
            ? adj[paths[i][0]]
            : new List<int>();
          list.Add(paths[i][1]);
          adj[paths[i][0]] = list;
        }
      }
    }
 
    // Function to find the shortest path
    static int MinPath(int[][] paths, int[] A, int N, int E)
    {
      // If police is at either at
      // the 1-st house or at N-th house
      if (A[0] == 1 || A[N - 1] == 1)
 
        // The thief cannot reach
        // the N-th house
        return -1;
 
      // Stores Edges of graph
      Dictionary<int, List<int> > adj
        = new Dictionary<int, List<int> >();
 
      // Function call to store connections
      CreateGraph(adj, paths, A, N, E);
 
      // Stores whether node is
      // visited or not
      bool[] visited = new bool[N];
 
      // Stores distances
      // from the root node
      int[] dist = new int[N];
      dist[0] = 0;
 
      Queue<int> q = new Queue<int>();
      q.Enqueue(0);
      visited[0] = true;
 
      // Visit all nodes that are
      // currently in the queue
      while (q.Count > 0) {
        int temp = q.Dequeue();
 
        if (adj.ContainsKey(temp)) {
          foreach(int x in adj[temp])
          {
            // If current node is
            // not visited already
            if (!visited[x]) {
              q.Enqueue(x);
 
              visited[x] = true;
              dist[x] = dist[temp] + 1;
            }
          }
        }
      }
 
      if (!visited[N - 1])
        return -1;
      else
        return dist[N - 1];
    }
  }
 
}
 
// This code is contributed by phasing17.

Javascript

<script>
 
// Javascript program for the above approach
 
 // Stores Edges of graph
 var adj = new Map();
 
// Function to create graph edges
// where node A and B can be visited
function createGraph(paths, A, N, E)
{
    // Visit all the connections
    for (var i = 0; i < E; i++) {
 
        // If a policeman is at any point of
        // connection, leave that connection.
        // Insert the connect otherwise.
        if (!A[paths[i][0]] && !A[paths[i][1]]) {
 
            if(adj.has(paths[i][0]))
            {
                var tmp = adj.get(paths[i][0]);
                tmp.push(paths[i][1]);
                adj.set(paths[i][0], tmp);
            }
            else
            {
                var tmp = new Array();
                tmp.push(paths[i][1]);
                adj.set(paths[i][0], tmp);
            }
        }
    }
}
 
// Function to find the shortest path
function minPath(paths, A, N, E)
{
    // If police is at either at
    // the 1-st house or at N-th house
    if (A[0] == 1 || A[N - 1] == 1)
 
        // The thief cannot reach
        // the N-th house
        return -1;
 
    // Function call to store connections
    createGraph(paths, A, N, E);
 
    // Stores whether node is
    // visited or not
    var visited = Array(N).fill(0);
 
    // Stores distances
    // from the root node
    var dist = Array(N).fill(0);
    dist[0] = 0;
 
    var q = [];
    q.push(0);
    visited[0] = 1;
 
    // Visit all nodes that are
    // currently in the queue
    while (q.length!=0) {
 
        var temp = q[0];
        q.pop();
 
        if(adj.has(temp))
        {
        for (var x of adj.get(temp)) {
 
            // If current node is
            // not visited already
            if (!visited[x]) {
 
                q.push(x);
                visited[x] = 1;
                dist[x] = dist[temp] + 1;
            }
        }
    }
    }
 
    if (!visited[N - 1])
        return -1;
    else
        return dist[N - 1];
}
 
// Driver Code
// N : Number of houses
// E: Number of edges
var N = 5, E = 5;
 
// Given positions
var A = [0, 1, 0, 0, 0 ];
 
// Given Paths
var paths = [ [ 0, 1 ],
                   [ 0, 2 ],
                   [ 1, 4 ],
                   [ 2, 3 ],
                   [ 3, 4 ] ];
// Function call
document.write(minPath(paths, A, N, E));
 
// This code is contributed by itsok.
</script>

Output:

Time complexity: O (N + E)
Auxiliary Space: O (N + E)

Reffered: https://www.geeksforgeeks.org

Graph

Related
Maximum Bitwise XOR of node values of an Acyclic Graph made up of N given vertices using M edges
Maximum cost path from source node to destination node via at most K intermediate nodes
Java Program to Implement of Gabow Scaling Algorithm
Path from a given source to a given destination having Kth largest weight in a Graph
Connect a graph by M edges such that the graph does not contain any cycle and Bitwise AND of connected vertices is maximum

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12