Queries on Graph for finding shortest path with maximum coins
Given an unweighted directed graph with N vertices and M edges and array A[] of size N. Given Q queries of the form (U, V), the task for this problem is for every query to print the shortest path from U to V and print the maximum coins collected for that shortest path. For visiting, Node ‘i’ collects A[i] coins. If traveling from U to V is not possible print -1.
Examples:
Input: N = 5, Edg[] = {{1, 2}, {1, 3}, {2, 3}, {3, 4}, {3, 5}, {4, 1}, {5, 1}}, A[] = {30, 50, 70, 20, 60}, Q[] = {{1, 3}, {3, 1}, {4, 5}};
Output: 1 100
2 160
3 180
Explanation:
- Length of Shortest path from 1 to 3 is 1 (1 -> 3) and coins collected = coins at node1 + coins at node3 = 30 + 70 = 100
- Length of Shortest path from 3 to 1 is 2 (3 -> 5 -> 1) and coins collected = coins at node3 + coins at node5 + coins at node1 = 70 + 60 + 30 = 160
- Length of Shortest path from 4 to 5 is 3 (4 -> 1 -> 3 -> 5) and coins collected = coins at node4 + coins at node1 + coins at node3 + coins at node5 = 20 + 30 + 70 + 60 = 180
Input: N2 = 2, Edg[] = {}, A[] = {100, 100}, Q[] = {{1, 2}}
Output: -1
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem
dp[i][j] represents shortest path from i to j.
Follow the steps below to solve the problem:
- Create dp[N][N] and ANS[N][N] tables with all values set to INT_MAX and INT_MIN.
- Iterate over all M edges and for each edge U and V set dp[U][V] to 1 and ANS[U][V] to A[U] + A[V].
- Fill the dp[N][N] table by iterating on all states.
- Iterate each query and print the answer
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // To avoid overflow #define int long long // Function for finding shortest paths // with maximized coins void shortPath( int N, vector<vector< int > >& edg, vector< int >& A, vector<vector< int > >& Q) { // Initializing dp table for // finding shortest path vector<vector< int > > dp(N + 1, vector< int >(N + 1, INT_MAX)); // Initializing another table // to store max coins vector<vector< int > > ans(N + 1, vector< int >(N + 1, INT_MIN)); // Iterating over all M edges for ( int i = 0; i < edg.size(); i++) { // There is edge exists from // edg[i][0] to edg[i][1] dp[edg[i][0]][edg[i][1]] = 1; // Answer variable stores ans[edg[i][0]][edg[i][1]] = A[edg[i][0] - 1] + A[edg[i][1] - 1]; } // Inserting from 1 to N for ( int k = 1; k <= N; k++) { // Iterating on all 1 to N for ( int i = 1; i <= N; i++) { // Iterating on all 1 to N for ( int j = 1; j <= N; j++) { // If path through k is // shortest then relax // the weight if (dp[i][j] > dp[i][k] + dp[k][j]) { dp[i][j] = dp[i][k] + dp[k][j]; ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } // Maximise coins else if (dp[i][j] == dp[i][k] + dp[k][j] and ans[i][j] < ans[i][k] + ans[k][j] - A[k - 1]) { ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } } } } // Iterating for all queries for ( int i = 0; i < Q.size(); i++) { // Query int U = Q[i][0], V = Q[i][1]; // Printing answer for query // if it exists if (dp[U][V] <= N * N) cout << dp[U][V] << " " << ans[U][V] << endl; // If no path exists else cout << "-1" << endl; } } // Driver program int32_t main() { // Test case 1 int N1 = 5; vector<vector< int > > edg1 = { { 1, 2 }, { 1, 3 }, { 2, 3 }, { 3, 4 }, { 3, 5 }, { 4, 1 }, { 5, 1 } }; vector< int > A1 = { 30, 50, 70, 20, 60 }; vector<vector< int > > Q1 = { { 1, 3 }, { 3, 1 }, { 4, 5 } }; // Call for test case 1 shortPath(N1, edg1, A1, Q1); cout << endl; // Test case 2 int N2 = 2; vector<vector< int > > edg2 = {}; vector< int > A2 = { 100, 100 }; vector<vector< int > > Q2 = { { 1, 2 } }; // Call for test case 2 shortPath(N2, edg2, A2, Q2); return 0; } |
Java
//Java code for the above approach import java.util.Arrays; class GFG { static void shortPath( int N, int [][] edg, int [] A, int [][] Q) { // Initializing dp table for finding shortest path int [][] dp = new int [N + 1 ][N + 1 ]; int [][] ans = new int [N + 1 ][N + 1 ]; for ( int i = 0 ; i < edg.length; i++) { dp[edg[i][ 0 ]][edg[i][ 1 ]] = 1 ; ans[edg[i][ 0 ]][edg[i][ 1 ]] = A[edg[i][ 0 ] - 1 ] + A[edg[i][ 1 ] - 1 ]; } // Initializing another table to store max coins for ( int k = 1 ; k <= N; k++) { for ( int i = 1 ; i <= N; i++) { for ( int j = 1 ; j <= N; j++) { if (dp[i][k] > 0 && dp[k][j] > 0 ) { // check if i and k, and k and j are // connected if (dp[i][j] == 0 || dp[i][j] > dp[i][k] + dp[k][j]) { dp[i][j] = dp[i][k] + dp[k][j]; ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1 ]; } else if (dp[i][j] == dp[i][k] + dp[k][j] && ans[i][j] < ans[i][k] + ans[k][j] - A[k - 1 ]) { ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1 ]; } } } } } for ( int i = 0 ; i < Q.length; i++) { // Printing answer for query // if it exists int U = Q[i][ 0 ]; int V = Q[i][ 1 ]; if (dp[U][V] > 0 && dp[U][V] <= N * N) { System.out.println(dp[U][V] + " " + ans[U][V]); } else { // If no path exists System.out.println( "-1" ); } } } // Driver program public static void main(String[] args) { // Test case 1 int N1 = 5 ; int [][] edg1 = { { 1 , 2 }, { 1 , 3 }, { 2 , 3 }, { 3 , 4 }, { 3 , 5 }, { 4 , 1 }, { 5 , 1 } }; int [] A1 = { 30 , 50 , 70 , 20 , 60 }; int [][] Q1 = { { 1 , 3 }, { 3 , 1 }, { 4 , 5 } }; // Call for test case 1 shortPath(N1, edg1, A1, Q1); System.out.println(); // Test case 2 int N2 = 2 ; int [][] edg2 = {}; int [] A2 = { 100 , 100 }; int [][] Q2 = {{ 1 , 2 }}; // Call for test case 2 shortPath(N2, edg2, A2, Q2); System.out.println(); } } // This code is contributed by Pushpesh Raj. |
Python3
#Python code for the above approach: import sys # To avoid overflow sys.setrecursionlimit( 10 * * 7 ) def shortPath(N, edg, A, Q): # Initializing dp table for # finding shortest path dp = [[ float ( "inf" ) for j in range (N + 1 )] for i in range (N + 1 )] # Initializing another table # to store max coins ans = [[ - sys.maxsize for j in range (N + 1 )] for i in range (N + 1 )] # Iterating over all M edges for i in range ( len (edg)): # There is edge exists from # edg[i][0] to edg[i][1] dp[edg[i][ 0 ]][edg[i][ 1 ]] = 1 # Answer variable stores ans[edg[i][ 0 ]][edg[i][ 1 ]] = A[edg[i][ 0 ] - 1 ] + A[edg[i][ 1 ] - 1 ] # Inserting from 1 to N for k in range ( 1 , N + 1 ): # Iterating on all 1 to N for i in range ( 1 , N + 1 ): # Iterating on all 1 to N for j in range ( 1 , N + 1 ): # If path through k is # shortest then relax # the weight if dp[i][j] > dp[i][k] + dp[k][j]: dp[i][j] = dp[i][k] + dp[k][j] ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1 ] # Maximise coins elif (dp[i][j] = = dp[i][k] + dp[k][j] and ans[i][j] < ans[i][k] + ans[k][j] - A[k - 1 ]): ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1 ] # Iterating for all queries for i in range ( len (Q)): # Query U = Q[i][ 0 ] V = Q[i][ 1 ] # Printing answer for query # if it exists if dp[U][V] < = N * N: print (dp[U][V], ans[U][V]) # If no path exists else : print ( "-1" ) # Test case 1 N1 = 5 edg1 = [[ 1 , 2 ], [ 1 , 3 ], [ 2 , 3 ], [ 3 , 4 ], [ 3 , 5 ], [ 4 , 1 ], [ 5 , 1 ]] A1 = [ 30 , 50 , 70 , 20 , 60 ] Q1 = [[ 1 , 3 ], [ 3 , 1 ], [ 4 , 5 ]] # Call for test case 1 shortPath(N1, edg1, A1, Q1) print () # Test case 2 N2 = 2 edg2 = [] A2 = [ 100 , 100 ] Q2 = [[ 1 , 2 ]] #Call for test case 2 shortPath(N2, edg2, A2, Q2) print () #This code is contributed by shivamsharma215 |
C#
// C# code for the above approach: using System; class Program { static void shortPath( int N, int [][] edg, int [] A, int [][] Q) { // Initializing dp table for finding shortest path var dp = new int [N + 1, N + 1]; var ans = new int [N + 1, N + 1]; for ( var i = 0; i < edg.Length; i++) { dp[edg[i][0], edg[i][1]] = 1; ans[edg[i][0], edg[i][1]] = A[edg[i][0] - 1] + A[edg[i][1] - 1]; } // Initializing another table to store max coins for ( var k = 1; k <= N; k++) { for ( var i = 1; i <= N; i++) { for ( var j = 1; j <= N; j++) { if (dp[i, k] > 0 && dp[k, j] > 0) { // check if i and k, and k and j are // connected if (dp[i, j] == 0 || dp[i, j] > dp[i, k] + dp[k, j]) { dp[i, j] = dp[i, k] + dp[k, j]; ans[i, j] = ans[i, k] + ans[k, j] - A[k - 1]; } else if (dp[i, j] == dp[i, k] + dp[k, j] && ans[i, j] < ans[i, k] + ans[k, j] - A[k - 1]) { ans[i, j] = ans[i, k] + ans[k, j] - A[k - 1]; } } } } } for ( var i = 0; i < Q.Length; i++) { // Printing answer for query // if it exists var U = Q[i][0]; var V = Q[i][1]; if (dp[U, V] > 0 && dp[U, V] <= N * N) { Console.WriteLine(dp[U, V] + " " + ans[U, V]); } else { // If no path exists Console.WriteLine( "-1" ); } } } // Driver program static void Main() { // Test case 1 var N1 = 5; var edg1 = new int [][] { new int [] { 1, 2 }, new int [] { 1, 3 }, new int [] { 2, 3 }, new int [] { 3, 4 }, new int [] { 3, 5 }, new int [] { 4, 1 }, new int [] { 5, 1 } }; var A1 = new int [] { 30, 50, 70, 20, 60 }; var Q1 = new int [][] { new int [] { 1, 3 }, new int [] { 3, 1 }, new int [] { 4, 5 } }; shortPath(N1, edg1, A1, Q1); // Call for test case 1 Console.WriteLine(); // Test case 2 var N2 = 2; var edg2 = new int [0][]; var A2 = new int [] { 100, 100 }; var Q2 = new int [][] { new int [] { 1, 2 } }; // Call for test case 2 shortPath(N2, edg2, A2, Q2); Console.WriteLine(); } } |
Javascript
// JavaScript code for the above approach: // Function for finding shortest paths // with maximized coins function shortPath(N, edg, A, Q) { // Initializing dp table for // finding shortest path var dp = Array.from({length: N+1}, () => Array(N+1).fill(Number.POSITIVE_INFINITY)); // Initializing another table // to store max coins var ans = Array.from({length: N+1}, () => Array(N+1).fill(-Infinity)); // Iterating over all M edges for ( var i = 0; i < edg.length; i++) { // There is edge exists from // edg[i][0] to edg[i][1] dp[edg[i][0]][edg[i][1]] = 1; // Answer variable stores ans[edg[i][0]][edg[i][1]] = A[edg[i][0] - 1] + A[edg[i][1] - 1]; } // Inserting from 1 to N for ( var k = 1; k <= N; k++) { // Iterating on all 1 to N for ( var i = 1; i <= N; i++) { // Iterating on all 1 to N for ( var j = 1; j <= N; j++) { // If path through k is // shortest then relax // the weight if (dp[i][j] > dp[i][k] + dp[k][j]) { dp[i][j] = dp[i][k] + dp[k][j]; ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } // Maximise coins else if (dp[i][j] == dp[i][k] + dp[k][j] && ans[i][j] < ans[i][k] + ans[k][j] - A[k - 1]) { ans[i][j] = ans[i][k] + ans[k][j] - A[k - 1]; } } } } // Iterating for all queries for ( var i = 0; i < Q.length; i++) { // Query var U = Q[i][0]; var V = Q[i][1]; // Printing answer for query // if it exists if (dp[U][V] <= N * N) { console.log(dp[U][V], ans[U][V]); } // If no path exists else { console.log( "-1" ); } } } // Driver program // Test case 1 var N1 = 5; var edg1 = [[1, 2], [1, 3], [2, 3], [3, 4], [3, 5], [4, 1], [5, 1]]; var A1 = [30, 50, 70, 20, 60]; var Q1 = [[1, 3], [3, 1], [4, 5]]; // Call for test case 1 shortPath(N1, edg1, A1, Q1); console.log(); // Test case 2 var N2 = 2; var edg2 = []; var A2 = [100, 100]; var Q2 = [[1, 2]]; // Call for test case 2 shortPath(N2, edg2, A2, Q2); console.log(); // This code is contributed by Prasad Kandekar(prasad264) |
1 100 2 160 3 180 -1
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Related Articles:
Contact Us