Given a directed and weighted graph of N nodes and M edges, the task is to count the number of shortest length paths between node 1 to N.
Examples:
Input: N = 4, M = 5, edges = {{1, 4, 5}, {1, 2, 4}, {2, 4, 5}, {1, 3, 2}, {3, 4, 3}}
Output: 2
Explanation: The number of shortest path from node 1 to node 4 is 2, having cost 5.
Input: N = 3, M = 2, edges = {{1, 2, 4}, {1, 3, 5}}
Output: 1
Approach: The problem can be solved by the Dijkstra algorithm. Use two arrays, say dist[] to store the shortest distance from the source vertex and paths[] of size N, to store the number of different shortest paths from the source vertex to vertex N. Follow these steps below for the approach.
- Initialize a priority queue, say pq, to store the vertex number and its distance value.
- Initialize a vector of zeroes, say paths[] of size N, and make paths[1] equals 1.
- Initialize a vector of large numbers(1e9), say dist[] of size N, and make dist[1] equal 0.
- Iterate while pq is not empty.
- Pop from the pq and store the vertex value in a variable, say u, and the distance value in the variable d.
- If d is greater than u, then continue.
- For every v of each vertex u, if dist[v] > dist[u]+ (edge cost of u and v), then decrease the dist[v] to dist[u] +(edge cost of u and v) and assign the number of paths of vertex u to the number of paths of vertex v.
- For every v of each vertex u, if dist[v] = dist[u] + (edge cost of u and v), then add the number of paths of vertex u to the number of paths of vertex v.
- Finally, print paths[N].
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;const int MAXN = 1e5 + 1;vector<vector<pair<int, int> > > g(MAXN);vector<int> dist(MAXN);vector<int> route(MAXN);// Function to count number of shortest// paths from node 1 to node Nvoid countDistinctShortestPaths( int n, int m, int edges[][3]){ // Storing the graph for (int i = 0; i < m; ++i) { int u = edges[i][0], v = edges[i][1], c = edges[i][2]; g[u].push_back({ v, c }); } // Initializing dis array to a // large value for (int i = 2; i <= n; ++i) { dist[i] = INF; } // Initialize a priority queue priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; pq.push({ 0, 1 }); // Base Cases dist[1] = 0; route[1] = 1; // Loop while priority queue is // not empty while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); // if d is greater than distance // of the node if (d > dist[u]) continue; // Traversing all its neighbours for (auto e : g[u]) { int v = e.first; int c = e.second; if (c + d > dist[v]) continue; // Path found of same distance if (c + d == dist[v]) { route[v] += route[u]; } // New path found for lesser // distance if (c + d < dist[v]) { dist[v] = c + d; route[v] = route[u]; // Pushing in priority // queue pq.push({ dist[v], v }); } } }}// Driver Codeint main(){ // Given Input int n = 4; int m = 5; int edges[m][3] = { { 1, 4, 5 }, { 1, 2, 4 }, { 2, 4, 5 }, { 1, 3, 2 }, { 3, 4, 3 } }; // Function Call countDistinctShortestPaths(n, m, edges); cout << route[n] << endl; return 0;} |
Python3
# Python3 program for the above approachfrom queue import PriorityQueuefrom collections import defaultdictimport sysINF = int(1e9)MAXN = int(1e5 + 1)# A function to count the number of shortest paths from node 1 to node Ndef countDistinctShortestPaths(n, m, edges): # Storing the graph using adjacency list g = defaultdict(list) for i in range(m): u, v, c = edges[i] g[u].append((v, c)) # Initializing the distance array to a large value dist = [INF] * (n + 1) # Initializing the count array to store the number of shortest paths route = [0] * (n + 1) # Base Cases dist[1] = 0 route[1] = 1 # Initialize a priority queue pq = PriorityQueue() pq.put((0, 1)) # Loop while priority queue is not empty while not pq.empty(): d, u = pq.get() # if d is greater than distance of the node if d > dist[u]: continue # Traversing all its neighbours for v, c in g[u]: if c + d > dist[v]: continue # Path found of same distance if c + d == dist[v]: route[v] += route[u] # New path found for lesser distance if c + d < dist[v]: dist[v] = c + d route[v] = route[u] # Pushing in priority queue pq.put((dist[v], v)) # Return the number of shortest paths from node 1 to node N return route[n]# Driver Codeif __name__ == "__main__": # Given Input n = 4 m = 5 edges = [(1, 4, 5), (1, 2, 4), (2, 4, 5), (1, 3, 2), (3, 4, 3)] # Function Call result = countDistinctShortestPaths(n, m, edges) print(result) |
Javascript
// Function to count number of shortest// paths from node 1 to node Nfunction countDistinctShortestPaths(n, m, edges) { let g = []; let dist = []; let route = []; // Storing the graph for (let i = 0; i < m; i++) { let u = edges[i][0]; let v = edges[i][1]; let c = edges[i][2]; if (!g[u]) { g[u] = []; } g[u].push([v, c]); } // Initializing dis array to a // large value for (let i = 2; i <= n; i++) { dist[i] = Number.MAX_SAFE_INTEGER; } // Base Cases dist[1] = 0; route[1] = 1; // Loop while priority queue is // not empty let pq = []; pq.push([0, 1]); while (pq.length > 0) { let d = pq[0][0]; let u = pq[0][1]; pq.shift(); // if d is greater than distance // of the node if (d > dist[u]) continue; // Traversing all its neighbours if (g[u]) { for (let i = 0; i < g[u].length; i++) { let v = g[u][i][0]; let c = g[u][i][1]; if (c + d > dist[v]) continue; // Path found of same distance if (c + d === dist[v]) { route[v] += route[u]; } // New path found for lesser // distance if (c + d < dist[v]) { dist[v] = c + d; route[v] = route[u]; // Pushing in priority // queue pq.push([dist[v], v]); } } } } console.log(route[n]);}// Given Inputlet n = 4;let m = 5;let edges = [[1, 4, 5], [1, 2, 4], [2, 4, 5], [1, 3, 2], [3, 4, 3]];// Function CallcountDistinctShortestPaths(n, m, edges); |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to count number of shortest paths from node // 1 to node N static void countDistinctShortestPaths(int n, int m, int[][] edges) { List<int[]>[] g = new List[n + 1]; int[] dist = new int[n + 1]; int[] route = new int[n + 1]; // Storing the graph for (int i = 0; i < m; i++) { int u = edges[i][0]; int v = edges[i][1]; int c = edges[i][2]; if (g[u] == null) { g[u] = new ArrayList<int[]>(); } g[u].add(new int[] { v, c }); } // Initializing dis array to a large value Arrays.fill(dist, Integer.MAX_VALUE); // Base Cases dist[1] = 0; route[1] = 1; // Loop while priority queue is not empty PriorityQueue<int[]> pq = new PriorityQueue<>( Comparator.comparingInt(a -> a[0])); pq.add(new int[] { 0, 1 }); while (!pq.isEmpty()) { int[] poll = pq.poll(); int d = poll[0]; int u = poll[1]; // if d is greater than distance of the node if (d > dist[u]) continue; // Traversing all its neighbours if (g[u] != null) { for (int i = 0; i < g[u].size(); i++) { int[] edge = g[u].get(i); int v = edge[0]; int c = edge[1]; if (c + d > dist[v]) continue; // Path found of same distance if (c + d == dist[v]) { route[v] += route[u]; } // New path found for lesser distance if (c + d < dist[v]) { dist[v] = c + d; route[v] = route[u]; // Pushing in priority queue pq.add(new int[] { dist[v], v }); } } } } System.out.println(route[n]); } public static void main(String[] args) { // Given Input int n = 4; int m = 5; int[][] edges = { { 1, 4, 5 }, { 1, 2, 4 }, { 2, 4, 5 }, { 1, 3, 2 }, { 3, 4, 3 } }; // Function Call countDistinctShortestPaths(n, m, edges); }}// This code is contributed by karthik. |
Output:
2
Time Complexity: O(MLogN)
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!
