Number of ways to reach at destination in shortest time
Given an integer n and a 2D integer array of edges where edges[i] = [ui, vi, timei] means that there is an edge between intersections ui and vi that takes time i to reach. You want to know in how many ways you can travel from intersection 0 to intersection n – 1 in the shortest amount of time, the task is to return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 109 + 7.
Examples:
Input: n = 7, m = 10, edges[][] = [[0, 6, 7], [0, 1, 2], [1, 2, 3], [1, 3, 3], [6, 3, 3], [3, 5, 1], [6, 5, 1], [2, 5, 1], [0, 4, 5], [4, 6, 2]]
Output: 4
Explanation: The four ways to get there in 7 minutes are:
– 0 6
– 0 4 6
– 0 1 2 5 6
– 0 1 3 5 6Input: n = 6, m = 8, edges[][] = [[0, 5, 8], [0, 2, 2], [0, 1, 1], [1, 3, 3], [1, 2, 3], [2, 5, 6], [3, 4, 2], [4, 5, 2]]
Output: 3
Explanation: The three ways to get there in 8 minutes are:
– 0 5
– 0 2 5
– 0 1 3 4 5
Naive Approach: The basic way to solve the problem is as follows:
The goal is to travel from intersection 0 to intersection n-1 in the least period of time possible. To determine the shortest route from the 0 to n – 1 intersection, we can apply the Dijkstra algorithm. With the Dijkstra algorithm, we identify the intersection with the shortest trip time and one that has not been visited before minimizing the distance to its adjacent intersection. Because there can only be a maximum of (n-1) edges between two intersections, we shall repeat this process n times. Here, we maintain an array time[] where time[i] is the shortest distance between intersections 0 and it. We also maintain another array of ways[i] that represent the number of ways we can get to the ith junction from 0 intersections in the shortest amount of time possible ways[i]. Let’s take time_taken(u, v) denotes the time taken to go v intersection from the u intersection. Now there are two cases
- If (time[u] + time_taken(u, v) < time[v]) , then ways[v] = ways[u]
- if (time[u] + time_taken(u, v) == time[v]), then ways[v] = ways[v] + ways[u]
Efficient Approach: The optimized approach is as follows:
A min-heap can now be used effectively to obtain the intersection with the shortest journey time, as was discussed in the prior method. Once we begin reducing trip time, we add those junctions to a priority queue and choose the one with the shortest journey time.
Steps involved in the implementation of code:
- With the roads array, we first create an adjacency list.
- We now build a min heap that stores the intersection number and minimal time to travel to the intersection.
- Now, each time, we remove the crossing with the shortest travel time and reduce the time at its adjacent intersections.
- If ways[v] = ways[u] then (time[u]+time taken(u, v) time[v])
- if ways[v] = ways[v] + ways[u], then time[u] + time taken(u, v) == time[v].
Below is the code implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; int countPaths( int n, vector<vector< int > >& edges) { vector<vector<pair< int , int > > > graph(n + 1); for ( auto & edge : edges) { graph[edge[0]].push_back({ edge[1], edge[2] }); graph[edge[1]].push_back({ edge[0], edge[2] }); } vector< long long > distance(n, LLONG_MAX); vector< int > path(n); priority_queue<pair< long long , int >, vector<pair< long long , int > >, greater<pair< long long , int > > > pq; pq.push({ 0, 0 }); distance[0] = 0; path[0] = 1; while (!pq.empty()) { auto t = pq.top(); pq.pop(); int vertex = t.second; for ( auto & nbr : graph[vertex]) { int nbrVertex = nbr.first; int nbrEdge = nbr.second; if (distance[nbrVertex] > distance[vertex] + nbrEdge) { distance[nbrVertex] = distance[vertex] + nbrEdge; pq.push({ distance[nbrVertex], nbrVertex }); path[nbrVertex] = path[vertex] % MOD; } else if (distance[nbrVertex] == t.first + nbrEdge) { path[nbrVertex] += path[vertex]; path[nbrVertex] %= MOD; } } } return path[n - 1]; } int main() { int n = 7; vector<vector< int > > edges = { { 0, 6, 7 }, { 0, 1, 2 }, { 1, 2, 3 }, { 1, 3, 3 }, { 6, 3, 3 }, { 3, 5, 1 }, { 6, 5, 1 }, { 2, 5, 1 }, { 0, 4, 5 }, { 4, 6, 2 } }; int numPaths = countPaths(n, edges); cout << "Number of paths from 0 to " << n - 1 << ": " << numPaths << endl; return 0; } |
Java
// Java code of the above approach import java.util.*; public class GFG { // Function to calculate // number of ways static int countPaths( int n, List<List<Integer> > edges) { // Modulus for calculating answer double mod = 1e9 + 7 ; // Create graph representation List<List< int []> > graph = new ArrayList<>(); for ( int i = 0 ; i <= n; i++) { graph.add( new ArrayList<>()); } // Add edges to graph for (List<Integer> edge : edges) { graph.get(edge.get( 0 )) .add( new int [] { edge.get( 1 ), edge.get( 2 ) }); graph.get(edge.get( 1 )) .add( new int [] { edge.get( 0 ), edge.get( 2 ) }); } // Initialize distance array // and path array long [] distance = new long [n]; Arrays.fill(distance, Long.MAX_VALUE); int [] path = new int [n]; // Use priority queue to // traverse graph PriorityQueue< long []> pq = new PriorityQueue<>( (x, y) -> ( int )(x[ 0 ] - y[ 0 ])); // Start at vertex 0 pq.add( new long [] { 0 , 0 }); distance[ 0 ] = 0 ; path[ 0 ] = 1 ; // Traverse graph while (!pq.isEmpty()) { long [] t = pq.poll(); int vertex = ( int )t[ 1 ]; for ( int [] nbr : graph.get(vertex)) { int nbrVertex = nbr[ 0 ]; int nbrEdge = nbr[ 1 ]; // Update distance and // path arrays if (distance[nbrVertex] > distance[vertex] + nbrEdge) { distance[nbrVertex] = distance[vertex] + nbrEdge; pq.add( new long [] { distance[nbrVertex], nbrVertex }); path[nbrVertex] = path[vertex] % 1000000007 ; } else if (distance[nbrVertex] == t[ 0 ] + nbrEdge) { path[nbrVertex] += path[vertex]; path[nbrVertex] %= 1000000007 ; } } } // Return number of paths from // vertex 0 to vertex n-1 return path[n - 1 ]; } // Driver code public static void main(String[] args) { // Example usage int n = 7 ; List<List<Integer> > edges = Arrays.asList( Arrays.asList( 0 , 6 , 7 ), Arrays.asList( 0 , 1 , 2 ), Arrays.asList( 1 , 2 , 3 ), Arrays.asList( 1 , 3 , 3 ), Arrays.asList( 6 , 3 , 3 ), Arrays.asList( 3 , 5 , 1 ), Arrays.asList( 6 , 5 , 1 ), Arrays.asList( 2 , 5 , 1 ), Arrays.asList( 0 , 4 , 5 ), Arrays.asList( 4 , 6 , 2 )); // Function call int numPaths = countPaths(n, edges); System.out.println( "Number of paths from 0 to " + (n - 1 ) + ": " + numPaths); } } |
Python3
import heapq def count_paths(n, edges): mod = int ( 1e9 + 7 ) # Create graph representation graph = [[] for _ in range (n + 1 )] # Add edges to graph for edge in edges: graph[edge[ 0 ]].append([edge[ 1 ], edge[ 2 ]]) graph[edge[ 1 ]].append([edge[ 0 ], edge[ 2 ]]) # Initialize distance array and path array distance = [ float ( "inf" )] * n path = [ 0 ] * n # Use priority queue to traverse graph pq = [] heapq.heappush(pq, ( 0 , 0 )) distance[ 0 ] = 0 path[ 0 ] = 1 # Traverse graph while pq: t = heapq.heappop(pq) vertex = t[ 1 ] for nbr in graph[vertex]: nbr_vertex, nbr_edge = nbr # Update distance and path arrays if distance[nbr_vertex] > distance[vertex] + nbr_edge: distance[nbr_vertex] = distance[vertex] + nbr_edge heapq.heappush(pq, (distance[nbr_vertex], nbr_vertex)) path[nbr_vertex] = path[vertex] % mod elif distance[nbr_vertex] = = t[ 0 ] + nbr_edge: path[nbr_vertex] + = path[vertex] path[nbr_vertex] % = mod # Return number of paths from vertex 0 to vertex n-1 return path[n - 1 ] # Example usage n = 7 edges = [ [ 0 , 6 , 7 ], [ 0 , 1 , 2 ], [ 1 , 2 , 3 ], [ 1 , 3 , 3 ], [ 6 , 3 , 3 ], [ 3 , 5 , 1 ], [ 6 , 5 , 1 ], [ 2 , 5 , 1 ], [ 0 , 4 , 5 ], [ 4 , 6 , 2 ] ] # Function call num_paths = count_paths(n, edges) print ( "Number of paths from 0 to {}: {}" . format (n - 1 , num_paths)) # This code is contributed by sarojmcy2e |
C#
using System; using System.Collections.Generic; public class GFG { // Function to calculate number of ways static int countPaths( int n, List<List< int >> edges) { // Modulus for calculating answer double mod = 1e9 + 7; // Create graph representation List<List< int []>> graph = new List<List< int []>>(); for ( int i = 0; i <= n; i++) { graph.Add( new List< int []>()); } // Add edges to graph foreach (List< int > edge in edges) { graph[edge[0]].Add( new int [] { edge[1], edge[2] }); graph[edge[1]].Add( new int [] { edge[0], edge[2] }); } // Initialize distance array and path array long [] distance = new long [n]; Array.Fill(distance, long .MaxValue); int [] path = new int [n]; // Use priority queue to traverse graph PriorityQueue< long []> pq = new PriorityQueue< long []>((x, y) => ( int )(x[0] - y[0])); // Start at vertex 0 pq.Enqueue( new long [] { 0, 0 }); distance[0] = 0; path[0] = 1; // Traverse graph while (pq.Count() != 0) { long [] t = pq.Dequeue(); int vertex = ( int )t[1]; foreach ( int [] nbr in graph[vertex]) { int nbrVertex = nbr[0]; int nbrEdge = nbr[1]; // Update distance and path arrays if (distance[nbrVertex] > distance[vertex] + nbrEdge) { distance[nbrVertex] = distance[vertex] + nbrEdge; pq.Enqueue( new long [] { distance[nbrVertex], nbrVertex }); path[nbrVertex] = path[vertex] % 1000000007; } else if (distance[nbrVertex] == t[0] + nbrEdge) { path[nbrVertex] += path[vertex]; path[nbrVertex] %= 1000000007; } } } // Return number of paths from vertex 0 to vertex n-1 return path[n - 1]; } // Driver code public static void Main( string [] args) { // Example usage int n = 7; List<List< int >> edges = new List<List< int >> { new List< int > { 0, 6, 7 }, new List< int > { 0, 1, 2 }, new List< int > { 1, 2, 3 }, new List< int > { 1, 3, 3 }, new List< int > { 6, 3, 3 }, new List< int > { 3, 5, 1 }, new List< int > { 6, 5, 1 }, new List< int > { 2, 5, 1 }, new List< int > { 0, 4, 5 }, new List< int > { 4, 6, 2 } }; // Function call int numPaths = countPaths(n, edges); Console.WriteLine( "Number of paths from 0 to " + (n - 1) + ": " + numPaths); } } public class PriorityQueue<T> { private List<T> data; private Comparison<T> comparison; public PriorityQueue(Comparison<T> comparison) { this .data = new List<T>(); this .comparison = comparison; } public void Enqueue(T item) { data.Add(item); int i = data.Count - 1; while (i > 0) { int j = (i - 1) / 2; if (comparison(data[j], item) <= 0) break ; data[i] = data[j]; i = j; } data[i] = item; } public T Dequeue() { int lastIndex = data.Count - 1; T frontItem = data[0]; data[0] = data[lastIndex]; data.RemoveAt(lastIndex); --lastIndex; int i = 0; while ( true ) { int childIndex = i * 2 + 1; if (childIndex > lastIndex) break ; int rightChild = childIndex + 1; if (rightChild <= lastIndex && comparison(data[rightChild], data[childIndex]) < 0) childIndex = rightChild; if (comparison(data[i], data[childIndex]) <= 0) break ; T tmp = data[i]; data[i] = data[childIndex]; data[childIndex] = tmp; i = childIndex; } return frontItem; } public T Peek() { T frontItem = data[0]; return frontItem; } public int Count() { return data.Count; } } |
Javascript
function countPaths(n, edges) { const mod = 1e9 + 7; const graph = new Array(n + 1).fill().map(() => []); for (let i = 0; i < edges.length; i++) { const [u, v, w] = edges[i]; graph[u].push([v, w]); graph[v].push([u, w]); } const distance = new Array(n).fill(Number.MAX_SAFE_INTEGER); const path = new Array(n).fill(0); const pq = [[0, 0]]; distance[0] = 0; path[0] = 1; while (pq.length) { const [t, vertex] = pq.shift(); for (const [nbrVertex, nbrEdge] of graph[vertex]) { if (distance[nbrVertex] > distance[vertex] + nbrEdge) { distance[nbrVertex] = distance[vertex] + nbrEdge; pq.push([distance[nbrVertex], nbrVertex]); path[nbrVertex] = path[vertex] % mod; } else if (distance[nbrVertex] == t + nbrEdge) { path[nbrVertex] += path[vertex]; path[nbrVertex] %= mod; } } pq.sort((a, b) => a[0] - b[0]); } return path[n - 1]; } // Example usage const n = 7; const edges = [ [0, 6, 7], [0, 1, 2], [1, 2, 3], [1, 3, 3], [6, 3, 3], [3, 5, 1], [6, 5, 1], [2, 5, 1], [0, 4, 5], [4, 6, 2] ]; // Function call const numPaths = countPaths(n, edges); console.log(`Number of paths from 0 to ${n - 1}: ${numPaths}`); |
Number of paths from 0 to 6: 4
Time complexity: O(M+NlogN)
Auxiliary Space: O(M+N)
Contact Us