human
Number of minimum length paths between 1 to N including each node | 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"
Solution in Python:
assistant
#Here is code to number of minimum length paths between 1 to N including each node and the other steps required.
 def countMinDistance ( n , m , edges ) :
	g = [ [ ] for i in range ( 10005 ) ]
	for i in range ( m ) :
		a = edges [ i ] [ 0 ] - 1
		b = edges [ i ] [ 1 ] - 1
		g [ a ] . append ( b )
		g [ b ] . append ( a )
	queue1 = [ ]
	queue1 . append ( [ 0 , 0 ] )
	dist = [ 1e9 for i in range ( n ) ]
	ways1 = [ 0 for i in range ( n ) ]
	dist [ 0 ] = 0
	ways1 [ 0 ] = 1
	while ( len ( queue1 ) > 0 ) :
		up = queue1 [ 0 ]
		queue1 = queue1 [ : - 1 ]
		x = up [ 0 ]
		dis = up [ 1 ]
		if ( dis > dist [ x ] ) :
			continue
		if ( x == n - 1 ) :
			continue
		for y in g [ x ] :
			if ( dist [ y ] > dis + 1 ) :
				dist [ y ] = dis + 1
				ways1 [ y ] = ways1 [ x ]
				queue1 . append ( [ y , dis + 1 ] )
			elif ( dist [ y ] == dis + 1 ) :
				ways1 [ y ] += ways1 [ x ]
	queue2 = [ ]
	queue2 . append ( [ n - 1 , 0 ] )
	dist1 = [ 1e9 for i in range ( n ) ]
	ways2 = [ 0 for i in range ( n ) ]
	dist1 [ n - 1 ] = 0
	ways2 [ n - 1 ] = 1
	while ( len ( queue2 ) > 0 ) :
		up = queue2 [ 0 ]
		queue2 = queue2 [ : - 1 ]
		x = up [ 0 ]
		dis = up [ 1 ]
		if ( dis > dist1 [ x ] ) :
			continue
		if ( x == 0 ) :
			continue
		for y in g [ x ] :
			if ( dist1 [ y ] > dis + 1 ) :
				dist1 [ y ] = dis + 1
				ways2 [ y ] = ways2 [ x ]
				queue2 . append ( [ y , dis + 1 ] )
			elif ( dist1 [ y ] == 1 + dis ) :
				ways2 [ y ] += ways2 [ x ]
	ways1 [ n - 1 ] = 1
	ways2 [ n - 1 ] = 1
	for i in range ( n ) :
		print ( ways1 [ i ] * ways2 [ i ] , end = " ▁ " )
if __name__ == ' _ _ main _ _ ' :
	N = 5
	M = 5
	edges = [ [ 1 , 2 ] , [ 1 , 4 ] , [ 1 , 3 ] , [ 2 , 5 ] , [ 2 , 4 ] ]
	countMinDistance ( N , M , edges )