Number of 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 ; Stores the number of edges ; Storing the edges in vector ; Initialize queue ; BFS from 1 st node using queue ; Pop from queue ; Traversing the adjacency list ; Initialize queue ; BFS from last node ; Pop from queue ; Traverse the adjacency list ; Print the count of minimum distance ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE void countMinDistance ( 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 > > queue1 ; queue1 . push ( { 0 , 0 } ) ; vector < int > dist ( n , 1e9 ) ; vector < int > ways1 ( n , 0 ) ; dist [ 0 ] = 0 ; ways1 [ 0 ] = 1 ; while ( ! queue1 . empty ( ) ) { auto up = queue1 . front ( ) ; queue1 . pop ( ) ; int x = up . first ; int dis = up . second ; if ( dis > dist [ x ] ) continue ; if ( x == n - 1 ) continue ; for ( ll y : g [ x ] ) { if ( dist [ y ] > dis + 1 ) { dist [ y ] = dis + 1 ; ways1 [ y ] = ways1 [ x ] ; queue1 . push ( { y , dis + 1 } ) ; } else if ( dist [ y ] == dis + 1 ) { ways1 [ y ] += ways1 [ x ] ; } } } queue < pair < ll , ll > > queue2 ; queue2 . push ( { n - 1 , 0 } ) ; vector < int > dist1 ( n , 1e9 ) ; vector < int > ways2 ( n , 0 ) ; dist1 [ n - 1 ] = 0 ; ways2 [ n - 1 ] = 1 ; while ( ! queue2 . empty ( ) ) { auto up = queue2 . front ( ) ; queue2 . pop ( ) ; int x = up . first ; int dis = up . second ; if ( dis > dist1 [ x ] ) continue ; if ( x == 0 ) continue ; for ( ll y : g [ x ] ) { if ( dist1 [ y ] > dis + 1 ) { dist1 [ y ] = dis + 1 ; ways2 [ y ] = ways2 [ x ] ; queue2 . push ( { y , dis + 1 } ) ; } else if ( dist1 [ y ] == 1 + dis ) { ways2 [ y ] += ways2 [ x ] ; } } } for ( int i = 0 ; i < n ; i ++ ) { cout << ways1 [ i ] * ways2 [ i ] << " ▁ " ; } } int main ( ) { int N = 5 , M = 5 ; int edges [ M ] [ 2 ] = { { 1 , 2 } , { 1 , 4 } , { 1 , 3 } , { 2 , 5 } , { 2 , 4 } } ; countMinDistance ( N , M , edges ) ; return 0 ; }