Given an undirected graph consisting of N nodes and M edges, the task is to find the minimum length of the path from Node 1 to Node N passing from every possible node of the given graph. If there doesn’t exist any such path, then print -1.
Note: The path can pass through a node any number of times.
Examples:
Input: N = 4, M = 4, edges[][] = {{1, 2}, {2, 3}, {1, 3}, {2, 4}}
Output: 2 2 3 2
Explanation:
Minimum path length from 1 to 4, passing from 1 is 2.
Minimum path length from 1 to 4, passing from 2 is 2.
Minimum path length from 1 to 4, passing from 3 is 3.
Minimum path length from 1 to 4, passing from 4 is 2.Input: N = 5, M = 7, edges[][] = {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {4, 3}, {4, 5}, {1, 5}}
Output: 1 2 4 2 1
Approach: The idea is to run two BFS, one from node 1 excluding node N and another from node N excluding node 1 to find the minimum distance of all the nodes from 1 and N. The sum of both the minimum distances will be the minimum length of the path from 1 to N including the node. Follow the steps below to solve the problem:
- Initialize a queue, say queue1 to perform BFS from node 1 and a queue queue2 to perform BFS from node N.
- Initialize two arrays, say dist1[] and dist2[] that store the shortest distance by performing BFS1 and BFS2.
- Perform two BFS and perform the following steps in each case:
- Pop from the queue and store node in x and its distance in dis.
- If dist[x] is smaller than dis then continue.
- Traverse the adjacency list of x and for each child y, if dist[y] is greater than dis + 1 then update dist[y] equals dis + 1.
- After populating the two arrays dist1[] and dist2[] in the above steps, iterate over the range [0, N] and if the sum of (dist1[i] + dist2[i]) is greater than 109 then print “-1” as their exists no such path. Otherwise, print the value of (dist1[i] + dist2[i]) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define ll long long int// Function to calculate the distances// from node 1 to Nvoid minDisIncludingNode(int n, int m, int edges[][2]){ // Vector to store our edges vector<ll> g[10005]; // Storing the edgees in the Vector for (int i = 0; i < m; i++) { int a = edges[i][0] - 1; int b = edges[i][1] - 1; g[a].push_back(b); g[b].push_back(a); } // Initialize queue queue<pair<ll, ll> > q; q.push({ 0, 0 }); vector<int> dist(n, 1e9); dist[0] = 0; // BFS from first node using queue while (!q.empty()) { auto up = q.front(); // Pop from queue q.pop(); int x = up.first; int lev = up.second; if (lev > dist[x]) continue; if (x == n - 1) continue; // Traversing its adjacency list for (ll y : g[x]) { if (dist[y] > lev + 1) { dist[y] = lev + 1; q.push({ y, lev + 1 }); } } } // Initialize queue queue<pair<ll, ll> > q1; q1.push({ n - 1, 0 }); vector<int> dist1(n, 1e9); dist1[n - 1] = 0; // BFS from last node using queue while (!q1.empty()) { auto up = q1.front(); // Pop from queue q1.pop(); int x = up.first; int lev = up.second; if (lev > dist1[x]) continue; if (x == 0) continue; // Traversing its adjacency list for (ll y : g[x]) { if (dist1[y] > lev + 1) { dist1[y] = lev + 1; q1.push({ y, lev + 1 }); } } } // Printing the minimum distance // including node i for (int i = 0; i < n; i++) { // If not reachable if (dist[i] + dist1[i] > 1e9) cout << -1 << " "; // Path exists else cout << dist[i] + dist1[i] << " "; }}// Driver Codeint main(){ // Given Input int n = 5; int m = 7; int edges[m][2] = { { 1, 2 }, { 1, 4 }, { 2, 3 }, { 2, 5 }, { 4, 3 }, { 4, 5 }, { 1, 5 } }; // Function Call minDisIncludingNode(n, m, edges); return 0;} |
Java
import java.util.*;public class Main { public static void minDisIncludingNode(int n, int m, int[][] edges) { // List to store our edges List<Integer>[] g = new ArrayList[10005]; for (int i = 0; i < 10005; i++) { g[i] = new ArrayList<Integer>(); } // Storing the edges in the List for (int i = 0; i < m; i++) { int a = edges[i][0] - 1; int b = edges[i][1] - 1; g[a].add(b); g[b].add(a); } // Initialize queue Queue<Integer> q = new LinkedList<>(); q.add(0); int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[0] = 0; // BFS from first node using queue while (!q.isEmpty()) { int x = q.poll(); if (x == n - 1) continue; // Traversing its adjacency list for (int y : g[x]) { if (dist[y] > dist[x] + 1) { dist[y] = dist[x] + 1; q.add(y); } } } // Initialize queue Queue<Integer> q1 = new LinkedList<>(); q1.add(n - 1); int[] dist1 = new int[n]; Arrays.fill(dist1, Integer.MAX_VALUE); dist1[n - 1] = 0; // BFS from last node using queue while (!q1.isEmpty()) { int x = q1.poll(); if (x == 0) continue; // Traversing its adjacency list for (int y : g[x]) { if (dist1[y] > dist1[x] + 1) { dist1[y] = dist1[x] + 1; q1.add(y); } } } // Printing the minimum distance // including node i for (int i = 0; i < n; i++) { // If not reachable if (dist[i] + dist1[i] > Integer.MAX_VALUE) System.out.print(-1 + " "); // Path exists else System.out.print(dist[i] + dist1[i] + " "); } } public static void main(String[] args) { // Given Input int n = 5; int m = 7; int[][] edges = { { 1, 2 }, { 1, 4 }, { 2, 3 }, { 2, 5 }, { 4, 3 }, { 4, 5 }, { 1, 5 } }; // Function Call minDisIncludingNode(n, m, edges); }} |
Python3
# Python 3 program for the above approach# Function to calculate the distances# from node 1 to Ndef minDisIncludingNode(n, m, edges): # Vector to store our edges g = [[] for i in range(10005)] # Storing the edgees in the Vector for i in range(m): a = edges[i][0] - 1 b = edges[i][1] - 1 g[a].append(b) g[b].append(a) # Initialize queue q = [] q.append([0, 0]) dist = [1e9 for i in range(n)] dist[0] = 0 # BFS from first node using queue while(len(q)>0): up = q[0] # Pop from queue q = q[1:] x = up[0] lev = up[1] if (lev > dist[x]): continue if (x == n - 1): continue # Traversing its adjacency list for y in g[x]: if (dist[y] > lev + 1): dist[y] = lev + 1 q.append([y, lev + 1]) # Initialize queue q1 = [] q1.append([n - 1, 0]) dist1 = [1e9 for i in range(n)] dist1[n - 1] = 0 # BFS from last node using queue while (len(q1) > 0): up = q1[0] # Pop from queue q1 = q1[1:] x = up[0] lev = up[1] if (lev > dist1[x]): continue if (x == 0): continue # Traversing its adjacency list for y in g[x]: if (dist1[y] > lev + 1): dist1[y] = lev + 1 q1.append([y, lev + 1]) # Printing the minimum distance # including node i for i in range(n): # If not reachable if (dist[i] + dist1[i] > 1e9): print(-1,end = " ") # Path exists else: print(dist[i] + dist1[i],end = " ")# Driver Codeif __name__ == '__main__': # Given Input n = 5 m = 7 edges = [[1, 2],[1, 4],[2, 3],[2, 5],[4, 3],[4, 5],[1, 5]] # Function Call minDisIncludingNode(n, m, edges) # This code is contributed by SURENDRA_GANGWAR. |
C#
using System;using System.Collections.Generic;class MainClass { public static void MinDisIncludingNode(int n, int m, int[][] edges) { // List to store our edges List<int>[] g = new List<int>[10005]; for (int i = 0; i < 10005; i++) { g[i] = new List<int>(); } // Storing the edges in the List for (int i = 0; i < m; i++) { int a = edges[i][0] - 1; int b = edges[i][1] - 1; g[a].Add(b); g[b].Add(a); } // Initialize queue Queue<int> q = new Queue<int>(); q.Enqueue(0); int[] dist = new int[n]; for (int i = 0; i < n; i++) { dist[i] = int.MaxValue; } dist[0] = 0; // BFS from first node using queue while (q.Count != 0) { int x = q.Dequeue(); if (x == n - 1) continue; // Traversing its adjacency list foreach (int y in g[x]) { if (dist[y] > dist[x] + 1) { dist[y] = dist[x] + 1; q.Enqueue(y); } } } // Initialize queue Queue<int> q1 = new Queue<int>(); q1.Enqueue(n - 1); int[] dist1 = new int[n]; for (int i = 0; i < n; i++) { dist1[i] = int.MaxValue; } dist1[n - 1] = 0; // BFS from last node using queue while (q1.Count != 0) { int x = q1.Dequeue(); if (x == 0) continue; // Traversing its adjacency list foreach (int y in g[x]) { if (dist1[y] > dist1[x] + 1) { dist1[y] = dist1[x] + 1; q1.Enqueue(y); } } } // Printing the minimum distance // including node i for (int i = 0; i < n; i++) { // If not reachable if (dist[i] + dist1[i] > int.MaxValue) Console.Write(-1 + " "); // Path exists else Console.Write(dist[i] + dist1[i] + " "); } } public static void Main(string[] args) { // Given Input int n = 5; int m = 7; int[][] edges = { new int[] { 1, 2 }, new int[] { 1, 4 }, new int[] { 2, 3 }, new int[] { 2, 5 }, new int[] { 4, 3 }, new int[] { 4, 5 }, new int[] { 1, 5 } }; // Function Call MinDisIncludingNode(n, m, edges); }} |
Javascript
<script>// Javascript program for the above approach// Function to calculate the distances// from node 1 to Nfunction minDisIncludingNode(n, m, edges) { // Vector to store our edges let g = new Array(10005).fill(0).map(() => []); // Storing the edgees in the Vector for (let i = 0; i < m; i++) { let a = edges[i][0] - 1; let b = edges[i][1] - 1; g[a].push(b); g[b].push(a); } // Initialize queue let q = []; q.push([0, 0]); dist = new Array(n).fill(1e9); dist[0] = 0; // BFS from first node using queue while (q.length > 0) { let up = q[0]; // Pop from queue q.pop(); let x = up[0]; let lev = up[1]; if (lev > dist[x]) continue; if (x == n - 1) continue; // Traversing its adjacency list for (let y of g[x]) { if (dist[y] > lev + 1) { dist[y] = lev + 1; q.push([y, lev + 1]); } } } // Initialize queue let q1 = []; q1.push([n - 1, 0]); let dist1 = new Array(n).fill(1e9); dist1[n - 1] = 0; // BFS from last node using queue while (q1.length > 0) { let up = q1[0]; // Pop from queue q1.pop(); let x = up[0]; let lev = up[1]; if (lev > dist1[x]) continue; if (x == 0) continue; // Traversing its adjacency list for (let y of g[x]) { if (dist1[y] > lev + 1) { dist1[y] = lev + 1; q1.push([y, lev + 1]); } } } // Printing the minimum distance // including node i for (let i = 0; i < n; i++) { // If not reachable if (dist[i] + dist1[i] > 1e9) document.write(-1 + " "); // Path exists else document.write(dist[i] + dist1[i] + " "); }}// Driver Code// Given Inputlet n = 5;let m = 7;let edges = [ [1, 2], [1, 4], [2, 3], [2, 5], [4, 3], [4, 5], [1, 5],];// Function CallminDisIncludingNode(n, m, edges);// This code is contributed by gfgking</script> |
Output:
1 2 4 2 1
Time Complexity: O(N + M)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
