Maximize shortest path between given vertices by adding a single edge | Java program for the above approach ; To store graph as adjacency list ; To store the shortest path ; Function that performs BFS Traversal ; Fill initially each distance as 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 ] ; Print minimum cost ; Driver code ; Given nodes and edges ; Sort the selected nodes ; Given edges ; Function Call
import java . util . * ; import java . lang . * ; class GFG { static int INF = ( int ) 1e9 + 7 ; static int N , M ; static ArrayList < ArrayList < Integer > > edges ; static int [ ] [ ] dist = new int [ 2 ] [ 200000 ] ; static void bfs ( int [ ] dist , int s ) { int [ ] q = new int [ 200000 ] ; Arrays . fill ( dist , INF ) ; int qh = 0 , qt = 0 ; q [ qh ++ ] = s ; dist [ s ] = 0 ; while ( qt < qh ) { int x = q [ qt ++ ] ; for ( Integer y : edges . get ( x ) ) { if ( dist [ y ] == INF ) { dist [ y ] = dist [ x ] + 1 ; q [ qh ++ ] = y ; } } } } static void shortestPathCost ( int selected [ ] , int K ) { ArrayList < int [ ] > data = new ArrayList < > ( ) ; bfs ( dist [ 0 ] , 0 ) ; bfs ( dist [ 1 ] , N - 1 ) ; for ( int i = 0 ; i < K ; i ++ ) { data . add ( new int [ ] { dist [ 0 ] [ selected [ i ] ] - dist [ 1 ] [ selected [ i ] ] , selected [ i ] } ) ; } Collections . sort ( data , ( a , b ) -> a [ 0 ] - b [ 0 ] ) ; int best = 0 ; int MAX = - INF ; for ( int [ ] it : data ) { int a = it [ 1 ] ; best = Math . max ( best , MAX + dist [ 1 ] [ a ] ) ; MAX = Math . max ( MAX , dist [ 0 ] [ a ] ) ; } System . out . println ( Math . min ( dist [ 0 ] [ N - 1 ] , best + 1 ) ) ; } public static void main ( String [ ] args ) { N = 5 ; M = 4 ; int K = 2 ; int selected [ ] = { 1 , 3 } ; Arrays . sort ( selected ) ; edges = new ArrayList < > ( ) ; for ( int i = 0 ; i < 200005 ; i ++ ) edges . add ( new ArrayList < Integer > ( ) ) ; edges . get ( 0 ) . add ( 1 ) ; edges . get ( 1 ) . add ( 0 ) ; edges . get ( 1 ) . add ( 2 ) ; edges . get ( 2 ) . add ( 1 ) ; edges . get ( 2 ) . add ( 3 ) ; edges . get ( 3 ) . add ( 2 ) ; edges . get ( 3 ) . add ( 4 ) ; edges . get ( 4 ) . add ( 3 ) ; shortestPathCost ( selected , K ) ; } }