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

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 u and E 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:

• Unique Paths
• Longest Path Directed Acyclic Graph
• Longest Path In A Tree
   

Recommended Readings:

• Detect cycle in directed graph
• Master Graph Algorithms for Competitive Programming
   

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!