human
Maximize shortest path between given vertices by adding a single edge | Function that performs BFS Traversal.
Fill initially each distance as INF fill ( dist , dist + N , INF ).
Perform BFS.
Traverse the current edges.
Update the distance.
Insert in queue.
Function that maximizes the shortest path between source and destination vertex by adding a single edge between given selected nodes.
To update the shortest distance between node 1 to other vertices.
To update the shortest distance between node N to other vertices.
Store the values x [ i ] - y [ i ].
Sort all the vectors of pairs.
Traverse data [ ].
Maximize x [ a ] - y [ b ].
Prminimum cost.
Driver Code.
Given nodes and edges.
Sort the selected nodes.
Given edges.
Function Call"
How can the above be solved in Python?
assistant
#Here is code to maximize shortest path between given vertices by adding a single edge and the other steps required.
 def bfs ( x , s ) :
	global edges , dist
	q = [ 0 for i in range ( 200000 ) ]
	qh , qt = 0 , 0
	q [ qh ] = s
	qh += 1
	dist [ x ] [ s ] = 0
	while ( qt < qh ) :
		xx = q [ qt ]
		qt += 1
		for y in edges [ xx ] :
			if ( dist [ x ] [ y ] == 10 ** 18 ) :
				dist [ x ] [ y ] = dist [ x ] [ xx ] + 1
				q [ qh ] = y
				qh += 1
def shortestPathCost ( selected , K ) :
	global dist , edges
	data = [ ]
	bfs ( 0 , 0 )
	bfs ( 1 , N - 1 )
	for i in range ( K ) :
		data . append ( [ dist [ 0 ] [ selected [ i ] ] - dist [ 1 ] [ selected [ i ] ] , selected [ i ] ] )
	data = sorted ( data )
	best = 0
	MAX = - 10 ** 18
	for it in data :
		a = it [ 1 ]
		best = max ( best , MAX + dist [ 1 ] [ a ] )
		MAX = max ( MAX , dist [ 0 ] [ a ] )
	print ( min ( dist [ 0 ] [ N - 1 ] , best + 1 ) )
if __name__ == ' _ _ main _ _ ' :
	edges = [ [ ] for i in range ( 5 ) ]
	dist = [ [ 10 ** 18 for i in range ( 1000005 ) ] for i in range ( 2 ) ]
	N , M = 5 , 4
	K = 2
	selected = [ 1 , 3 ]
	selected = sorted ( selected )
	edges [ 0 ] . append ( 1 )
	edges [ 1 ] . append ( 0 )
	edges [ 1 ] . append ( 2 )
	edges [ 2 ] . append ( 1 )
	edges [ 2 ] . append ( 3 )
	edges [ 3 ] . append ( 2 )
	edges [ 3 ] . append ( 4 )
	edges [ 4 ] . append ( 3 )
	shortestPathCost ( selected , K )