Given an undirected graph of N nodes and M vertices. You are also given a K edges as selected[]. The task to maximize the shortest path length between node 1 to node N by adding single edges between any two vertices from the given selected edges.
Note: You may add an edge between any two selected vertices who have already an edge between them.
Input: N = 5, M = 4, K = 2, selected[] = {2, 4}
Below is the given graph:
Output: 3
Explanation:
Before adding an edge between 2 and 4, the Shortest Path becomes: 1–>2–>3–>4–>5.
After adding an edge between 2 and 4, the Shortest Path becomes 1–>2–>4–>5. Below is the graph after adding edges. denoted by the dashed line.
Input: N = 5 M = 5 K = 3 selected[] = {1, 3, 5}
Below is the given graph:
Output: 3
Explanation:
We can add an edge between 3 and 5 as they have already an edge between them. so, the shortest path becomes 1–>2–>3–>5. Below is the graph after adding edges. denoted by the dashed line.
Approach: The idea is to use Breadth-First Search to find the distance from vertices 1 and N to each selected vertex. For selected vertex i, let xi denote the distance to node 1, and yi denote the distance to node N. Below are the steps:
- Maintain a 2D matrix(say dist[2][]) having 2 rows and N columns.
- In the first row, Maintain the shortest distance between node 1 and other vertices in the graph using BFS Traversal.
- In the second row, Maintain the shortest distance between node N and the other vertices of the graph using BFS Traversal.
- Now, choose two selected vertices a and b from selected[] to minimize the value of min(xa + yb, ya + xb). For this do the following:
- Create a vector of pairs and store the value of (xi – yi) with their respective selected node.
- Sort the above vector of pairs.
- Initialize best to 0 and max to -INF.
- Now traverse the above vector of pairs and for each selected node(say a) update the value of best to maximum of (best, max + dist[1][a]) and update max to maximum of (max, dist[0][a]).
- After the above operations the maximum of (dist[0][N-1] and best + 1) given the minimum shortest path.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int INF = 1e9 + 7;int N, M;// To store graph as adjacency listvector<int> edges[200005];// To store the shortest pathint dist[2][200000];// Function that performs BFS Traversalvoid bfs(int* dist, int s){ int q[200000]; // Fill initially each distance as INF fill(dist, dist + N, INF); int qh = 0, qt = 0; q[qh++] = s; dist[s] = 0; // Perform BFS while (qt < qh) { int x = q[qt++]; // Traverse the current edges for (int y : edges[x]) { if (dist[y] == INF) { // Update the distance dist[y] = dist[x] + 1; // Insert in queue q[qh++] = y; } } }}// Function that maximizes the shortest// path between source and destination// vertex by adding a single edge between// given selected nodesvoid shortestPathCost(int selected[], int K){ vector<pair<int, int> > data; // To update the shortest distance // between node 1 to other vertices bfs(dist[0], 0); // To update the shortest distance // between node N to other vertices bfs(dist[1], N - 1); for (int i = 0; i < K; i++) { // Store the values x[i] - y[i] data.emplace_back(dist[0][selected[i]] - dist[1][selected[i]], selected[i]); } // Sort all the vectors of pairs sort(data.begin(), data.end()); int best = 0; int MAX = -INF; // Traverse data[] for (auto it : data) { int a = it.second; best = max(best, MAX + dist[1][a]); // Maximize x[a] - y[b] MAX= max(MAX, dist[0][a]); } // Print minimum cost printf("%d\n", min(dist[0][N - 1], best + 1));}// Driver Codeint main(){ // Given nodes and edges N = 5, M = 4; int K = 2; int selected[] = { 1, 3 }; // Sort the selected nodes sort(selected, selected + K); // Given edges edges[0].push_back(1); edges[1].push_back(0); edges[1].push_back(2); edges[2].push_back(1); edges[2].push_back(3); edges[3].push_back(2); edges[3].push_back(4); edges[4].push_back(3); // Function Call shortestPathCost(selected, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;class GFG{ static int INF = (int)1e9 + 7; static int N, M; // To store graph as adjacency list static ArrayList<ArrayList<Integer>> edges; // To store the shortest path static int[][] dist = new int[2][200000]; // Function that performs BFS Traversal static void bfs(int[] dist, int s) { int[] q = new int[200000]; // Fill initially each distance as INF Arrays.fill(dist, INF); int qh = 0, qt = 0; q[qh++] = s; dist[s] = 0; // Perform BFS while (qt < qh) { int x = q[qt++]; // Traverse the current edges for(Integer y : edges.get(x)) { if (dist[y] == INF) { // Update the distance dist[y] = dist[x] + 1; // Insert in queue q[qh++] = y; } } } } // Function that maximizes the shortest // path between source and destination // vertex by adding a single edge between // given selected nodes static void shortestPathCost(int selected[], int K) { ArrayList<int[]> data = new ArrayList<>(); // To update the shortest distance // between node 1 to other vertices bfs(dist[0], 0); // To update the shortest distance // between node N to other vertices bfs(dist[1], N - 1); for(int i = 0; i < K; i++) { // Store the values x[i] - y[i] data.add(new int[]{dist[0][selected[i]] - dist[1][selected[i]], selected[i]}); } // Sort all the vectors of pairs Collections.sort(data, (a, b) -> a[0] - b[0]); int best = 0; int MAX = -INF; // Traverse data[] for(int[] it : data) { int a = it[1]; best = Math.max(best, MAX + dist[1][a]); // Maximize x[a] - y[b] MAX = Math.max(MAX, dist[0][a]); } // Print minimum cost System.out.println(Math.min(dist[0][N - 1], best + 1)); }// Driver codepublic static void main (String[] args){ // Given nodes and edges N = 5; M = 4; int K = 2; int selected[] = { 1, 3 }; // Sort the selected nodes Arrays.sort(selected); edges = new ArrayList<>(); for(int i = 0; i < 200005; i++) edges.add(new ArrayList<Integer>()); // Given edges 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); // Function Call shortestPathCost(selected, K); }}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function that performs BFS Traversaldef bfs(x, s): global edges, dist q = [0 for i in range(200000)] # Fill initially each distance as INF # fill(dist, dist + N, INF) qh, qt = 0, 0 q[qh] = s qh += 1 dist[x][s] = 0 # Perform BFS while (qt < qh): xx = q[qt] qt += 1 # Traverse the current edges for y in edges[xx]: if (dist[x][y] == 10**18): # Update the distance dist[x][y] = dist[x][xx] + 1 # Insert in queue q[qh] = y qh += 1# Function that maximizes the shortest# path between source and destination# vertex by adding a single edge between# given selected nodesdef shortestPathCost(selected, K): global dist, edges data = [] # To update the shortest distance # between node 1 to other vertices bfs(0, 0) # To update the shortest distance # between node N to other vertices bfs(1, N - 1) for i in range(K): # Store the values x[i] - y[i] data.append([dist[0][selected[i]]- dist[1][selected[i]], selected[i]]) # Sort all the vectors of pairs data = sorted(data) best = 0 MAX = -10**18 # Traverse data[] for it in data: a = it[1] best = max(best,MAX + dist[1][a]) # Maximize x[a] - y[b] MAX= max(MAX, dist[0][a]) # Print minimum cost print(min(dist[0][N - 1], best + 1))# Driver Codeif __name__ == '__main__': # Given nodes and edges 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] # Sort the selected nodes selected = sorted(selected) # Given edges 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) # Function Call shortestPathCost(selected, K) # This code is contributed by mohit kumar 29 |
C#
using System;using System.Linq;class Program{ static int N, M, K; static int[][] edges, dist; static int[] selected;//Function that performs BFS Traversal static void BFS(int x, int s) { int[] q = new int[200000]; // //Fill initially each distance as INF //fill(dist, dist + N, INF) int qh = 0, qt = 0; q[qh] = s; qh++; dist[x][s] = 0;//Perform BFS while (qt < qh) { int xx = q[qt]; qt++; for (int i = 0; i < edges[xx].Length; i++) { int y = edges[xx][i]; if (dist[x][y] == int.MaxValue) { dist[x][y] = dist[x][xx] + 1; q[qh] = y; qh++; } } } } // Function that maximizes the shortest// path between source and destination// vertex by adding a single edge between// given selected nodes static void ShortestPathCost(int[] selected, int K) { BFS(0, 0); BFS(1, N - 1); Tuple<int, int>[] data = new Tuple<int, int>[K]; for (int i = 0; i < K; i++) { data[i] = Tuple.Create(dist[0][selected[i]] - dist[1][selected[i]], selected[i]); } Array.Sort(data, (a, b) => a.Item1.CompareTo(b.Item1)); int best = 0, MAX = int.MinValue; foreach (Tuple<int, int> it in data) { int a = it.Item2; best = Math.Max(best, MAX + dist[1][a]); MAX = Math.Max(MAX, dist[0][a]); } Console.WriteLine(Math.Min(dist[0][N - 1], best + 1)); }//Driver code static void Main(string[] args) { N = 5; M = 4; K = 2; selected = new int[] { 1, 3 }; Array.Sort(selected); edges = new int[5][]; edges[0] = new int[] { 1 }; edges[1] = new int[] { 0, 2 }; edges[2] = new int[] { 1, 3 }; edges[3] = new int[] { 2, 4 }; edges[4] = new int[] { 3 }; dist = new int[2][]; dist[0] = Enumerable.Repeat(int.MaxValue, 1000005).ToArray(); dist[1] = Enumerable.Repeat(int.MaxValue, 1000005).ToArray(); ShortestPathCost(selected, K); }} |
Javascript
<script>// Javascript program for the above approachlet INF = 1e9 + 7;let N, M;// To store graph as adjacency listlet edges=[];// To store the shortest pathlet 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 that performs BFS Traversalfunction bfs(dist,s){ let q = new Array(200000); // Fill initially each distance as INF let qh = 0, qt = 0; q[qh++] = s; dist[s] = 0; // Perform BFS while (qt < qh) { let x = q[qt++]; // Traverse the current edges for(let y=0;y< edges[x].length;y++) { if (dist[edges[x][y]] == INF) { // Update the distance dist[edges[x][y]] = dist[x] + 1; // Insert in queue q[qh++] = edges[x][y]; } } }}// Function that maximizes the shortest// path between source and destination// vertex by adding a single edge between// given selected nodes function shortestPathCost(selected,K){ let data = []; // To update the shortest distance // between node 1 to other vertices bfs(dist[0], 0); // To update the shortest distance // between node N to other vertices bfs(dist[1], N - 1); for(let i = 0; i < K; i++) { // Store the values x[i] - y[i] data.push([dist[0][selected[i]] - dist[1][selected[i]], selected[i]]); } // Sort all the vectors of pairs data.sort(function(a, b){return a[0] - b[0];}); let best = 0; let MAX = -INF; // Traverse data[] for(let it=0;it< data.length;it++) { let a = data[it][1]; best = Math.max(best, MAX + dist[1][a]); // Maximize x[a] - y[b] MAX = Math.max(MAX, dist[0][a]); } // Print minimum cost document.write(Math.min(dist[0][N - 1], best + 1));}// Driver code// Given nodes and edges N = 5; M = 4; let K = 2; let selected = [ 1, 3 ]; // Sort the selected nodes (selected).sort(function(a,b){return a-b;}); edges = []; for(let i = 0; i < 200005; i++) edges.push([]); // Given edges 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); // Function Call shortestPathCost(selected, K);// This code is contributed by patel2127</script> |
Output:
3
Time Complexity: O(N*log N + M)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
