Maximize shortest path between given vertices by adding a single edge | Javascript 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 ; Given nodes and edges ; Sort the selected nodes ; Given edges ; Function Call
let INF = 1e9 + 7 ; let N , M ; let edges = [ ] ; let dist = new Array ( 2 ) ; for ( let i = 0 ; i < 2 ; i ++ ) { dist [ i ] = new Array ( 200000 ) ; for ( let j = 0 ; j < 200000 ; j ++ ) { dist [ i ] [ j ] = INF ; } } function bfs ( dist , s ) { let q = new Array ( 200000 ) ; let qh = 0 , qt = 0 ; q [ qh ++ ] = s ; dist [ s ] = 0 ; while ( qt < qh ) { let x = q [ qt ++ ] ; for ( let y = 0 ; y < edges [ x ] . length ; y ++ ) { if ( dist [ edges [ x ] [ y ] ] == INF ) { dist [ edges [ x ] [ y ] ] = dist [ x ] + 1 ; q [ qh ++ ] = edges [ x ] [ y ] ; } } } } function shortestPathCost ( selected , K ) { let data = [ ] ; bfs ( dist [ 0 ] , 0 ) ; bfs ( dist [ 1 ] , N - 1 ) ; for ( let i = 0 ; i < K ; i ++ ) { data . push ( [ dist [ 0 ] [ selected [ i ] ] - dist [ 1 ] [ selected [ i ] ] , selected [ i ] ] ) ; } data . sort ( function ( a , b ) { return a [ 0 ] - b [ 0 ] ; } ) ; let best = 0 ; let MAX = - INF ; for ( let it = 0 ; it < data . length ; it ++ ) { let a = data [ it ] [ 1 ] ; best = Math . max ( best , MAX + dist [ 1 ] [ a ] ) ; MAX = Math . max ( MAX , dist [ 0 ] [ a ] ) ; } document . write ( Math . min ( dist [ 0 ] [ N - 1 ] , best + 1 ) ) ; } N = 5 ; M = 4 ; let K = 2 ; let selected = [ 1 , 3 ] ; ( selected ) . sort ( function ( a , b ) { return a - b ; } ) ; edges = [ ] ; for ( let i = 0 ; i < 200005 ; i ++ ) edges . push ( [ ] ) ; edges [ 0 ] . push ( 1 ) ; edges [ 1 ] . push ( 0 ) ; edges [ 1 ] . push ( 2 ) ; edges [ 2 ] . push ( 1 ) ; edges [ 2 ] . push ( 3 ) ; edges [ 3 ] . push ( 2 ) ; edges [ 3 ] . push ( 4 ) ; edges [ 4 ] . push ( 3 ) ; shortestPathCost ( selected , K ) ;