human
Minimum length paths between 1 to N including each node | 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"
How can the above be solved in Python?
assistant
#Here is code to minimum length paths between 1 to N including each node and the other steps required.
 def minDisIncludingNode ( 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 )
	q = [ ]
	q . append ( [ 0 , 0 ] )
	dist = [ 1e9 for i in range ( n ) ]
	dist [ 0 ] = 0
	while ( len ( q ) > 0 ) :
		up = q [ 0 ]
		q = q [ 1 : ]
		x = up [ 0 ]
		lev = up [ 1 ]
		if ( lev > dist [ x ] ) :
			continue
		if ( x == n - 1 ) :
			continue
		for y in g [ x ] :
			if ( dist [ y ] > lev + 1 ) :
				dist [ y ] = lev + 1
				q . append ( [ y , lev + 1 ] )
	q1 = [ ]
	q1 . append ( [ n - 1 , 0 ] )
	dist1 = [ 1e9 for i in range ( n ) ]
	dist1 [ n - 1 ] = 0
	while ( len ( q1 ) > 0 ) :
		up = q1 [ 0 ]
		q1 = q1 [ 1 : ]
		x = up [ 0 ]
		lev = up [ 1 ]
		if ( lev > dist1 [ x ] ) :
			continue
		if ( x == 0 ) :
			continue
		for y in g [ x ] :
			if ( dist1 [ y ] > lev + 1 ) :
				dist1 [ y ] = lev + 1
				q1 . append ( [ y , lev + 1 ] )
	for i in range ( n ) :
		if ( dist [ i ] + dist1 [ i ] > 1e9 ) :
			print ( - 1 , end = " ▁ " )
		else :
			print ( dist [ i ] + dist1 [ i ] , end = " ▁ " )
if __name__ == ' _ _ main _ _ ' :
	n = 5
	m = 7
	edges = [ [ 1 , 2 ] , [ 1 , 4 ] , [ 2 , 3 ] , [ 2 , 5 ] , [ 4 , 3 ] , [ 4 , 5 ] , [ 1 , 5 ] ]
	minDisIncludingNode ( n , m , edges )