Minimum length paths between 1 to N including each node | C ++ program for the above approach ; Function to calculate the distances from node 1 to N ; Vector to store our edges ; Storing the edgees in the Vector ; Initialize queue ; BFS from first node using queue ; Pop from queue ; Traversing its adjacency list ; Initialize queue ; BFS from last node using queue ; Pop from queue ; Traversing its adjacency list ; Printing the minimum distance including node i ; If not reachable ; Path exists ; Driver Code ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE void minDisIncludingNode ( int n , int m , int edges [ ] [ 2 ] ) { vector < ll > g [ 10005 ] ; 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 ) ; } queue < pair < ll , ll > > q ; q . push ( { 0 , 0 } ) ; vector < int > dist ( n , 1e9 ) ; dist [ 0 ] = 0 ; while ( ! q . empty ( ) ) { auto up = q . front ( ) ; q . pop ( ) ; int x = up . first ; int lev = up . second ; if ( lev > dist [ x ] ) continue ; if ( x == n - 1 ) continue ; for ( ll y : g [ x ] ) { if ( dist [ y ] > lev + 1 ) { dist [ y ] = lev + 1 ; q . push ( { y , lev + 1 } ) ; } } } queue < pair < ll , ll > > q1 ; q1 . push ( { n - 1 , 0 } ) ; vector < int > dist1 ( n , 1e9 ) ; dist1 [ n - 1 ] = 0 ; while ( ! q1 . empty ( ) ) { auto up = q1 . front ( ) ; q1 . pop ( ) ; int x = up . first ; int lev = up . second ; if ( lev > dist1 [ x ] ) continue ; if ( x == 0 ) continue ; for ( ll y : g [ x ] ) { if ( dist1 [ y ] > lev + 1 ) { dist1 [ y ] = lev + 1 ; q1 . push ( { y , lev + 1 } ) ; } } } for ( int i = 0 ; i < n ; i ++ ) { if ( dist [ i ] + dist1 [ i ] > 1e9 ) cout << -1 << " ▁ " ; else cout << dist [ i ] + dist1 [ i ] << " ▁ " ; } } int main ( ) { int n = 5 ; int m = 7 ; int edges [ m ] [ 2 ] = { { 1 , 2 } , { 1 , 4 } , { 2 , 3 } , { 2 , 5 } , { 4 , 3 } , { 4 , 5 } , { 1 , 5 } } ; minDisIncludingNode ( n , m , edges ) ; return 0 ; }