Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
2.
Sample Test Cases
3.
Approach
4.
Example
5.
Code
6.
Time Complexity
7.
Space Complexity
8.
FAQs
9.
Key Takeaways
Last Updated: Mar 27, 2024

Number of distinct Shortest Paths from Node 1 to N in a Weighted and Directed Graph

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Problem Statement

 

You are given a directed weighted graph having N nodes and M edges. You need to find the number of shortest paths from node 1 to N. 

Sample Test Cases

 

Input:
5 5
1 2 1
2 3 2
2 4 3
4 5 1
3 5 2

Output: 2

Explanation: The two paths are 1->2->3->5 and 1->2->4->5. See example for better understanding.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

 

To solve this problem, we can modify the Dijkstra algorithm. We can maintain an array to store the total number of distinct paths. 

Let 'length[]' be the array that stores the length of the shortest path and 'numPath[]' be the array that stores the total number of distinct paths for all the nodes.

Let node1 and node2 be the two nodes such that there is an edge from node1 to node2 of weight E then while processing node1 if length[node2] == length[node1] + E then we can increment numPath[node2] by numPath[node1] and if length[node2] > length[node1] + E then we can set numPath[node2] to numPath[node1].

 

Steps To Solve

Step 1 - Declare a priority queue, let say 'prq' of pairs to store distance and vertex value.

Step 2 - Declare two arrays or vector, length[] and numPath[] of size N + 1 each. Initialize all the elements of length[] and numPath[], by INF (a large number) and 0 respectively.

Step 3 - Implement the Dijkstra Algorithm. Set length[1] to 0 and numPath[1] to 1 and insert (0, 1) in the priority queue.

Step 4 - Iterate while prq is non-empty. Pop from the prq and vertex value in variable 'u' and distance in variable 'dis.'

Step 5 - if dis > length[u] then continue else process node u.

Step 6 - visit all the neighbors of u. Let 'v' be the neighbors of and be the edge weight of (u, v). Then if - 

  1. E + dis < length[v], then set length[v] to E + dis and numPath[v] to numPath[u].
  2. E + dis == length[v], then add numPath[u] to numPath[v]

Step 7 - numPath[N] is the final answer.

 

Example

 

 

                                                                           

 

Code

 

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
int countPaths(int N, vector <pair <int, int>> G[]){
   /*
   Declare two arrays or vector, length[] and numPath[] of size N + 1 each. 
   Initialize all the elements of length[] and numPath[], by INF (a large number) and 0 respectively.
   */
   vector <int> length(N + 1, INF);
   vector <int> numPath(N + 1, 0);
   
   //Declare a priority queue, let say 'prq' of pairs to store distance and vertex value.
   priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> prq;
   
   //Set length[1] to 0 and numPath[1] to 1
   length[1] = 0;
   numPath[1] = 1;
   //insert (0, 1) in the priority queue
   prq.push({0, 1});
   while(!prq.empty()){ //Iterate while prq is non-empty
       //Pop from the prq and vertex value in variable 'u' and distance in variable 'dis.'
       int u = prq.top().second;
       int dis = prq.top().first;
       prq.pop();
       //if dis > length[u] then continue else process node u
       if(dis > length[u])
           continue;
       //visit all the neighbors of u
       for(auto d : G[u]){
           int v = d.first;
           int E = d.second;
           //E + dis < length[v], then set length[v] to E + dis and numPath[v] to numPath[u], 
           //push (length[v], v) in priority queue.
           if(E + dis < length[v]){
               length[v] = E + dis;
               numPath[v] = numPath[u];
               prq.push({length[v], v});
           }
           else if(E + dis == length[v]){
               //E + dis == length[v], then add numPath[u] to numPath[v]. 
               numPath[v] += numPath[u];
           }
       }
   
   }
   //numPath[N] is the final answer
   return numPath[N];
}
int main(){
   int N, M;
   cin >> N >> M; //Numbers of Node, Edges
   vector <pair<int, int>> G[N + 1]; //Adjacency matrix
   for(int i = 0; i < M; i++){
       int u, v, E;
       cin >> u >> v >> E;
       G[u].push_back({v, E});
   }
   //function call
   cout << "Number of distinct Shortest Paths from Node 1 to " << N << " is " << countPaths(N, G) << "\n";
   return 0;
}

   

Time Complexity

 

The time complexity is O(M log N)

Space Complexity

 

The space complexity is O(N)

 

FAQs

  1. What is the Dijkstra algorithm? and what is its time complexity?
    The Dijkstra algorithm is used to find the shortest path from the source node to every other node in the graph. The time complexity is O(V + E log V), where V is the number of vertices in the graph and E is the number of edges. 
     
  2. What is priority queue?
    Priority queue is similar to queue, but in priority queue, the higher priority elements appear before lower priority elements. It is implemented using heap data structure.

Key Takeaways

In this article, we solved a graph theory problem. Having a good grasp of graph theory is very important for cracking coding interviews at MAANG. 

Recommended Problems:

Recommended Readings:

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!