Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Problem Statement
Sample Test Cases
Time Complexity
Space Complexity
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
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


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



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.









#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 =;
       int dis =;
       //if dis > length[u] then continue else process node u
       if(dis > length[u])
       //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)



  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!