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

0 0 6 minutes read

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 N
void 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 Code
int 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 approach
from queue import PriorityQueue
from collections import defaultdict
import sys
 
INF = int(1e9)
MAXN = int(1e5 + 1)
 
# A function to count the number of shortest paths from node 1 to node N
def 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 Code
if __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 N
function 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 Input
let n = 4;
let m = 5;
let edges = [[1, 4, 5],
    [1, 2, 4],
    [2, 4, 5],
    [1, 3, 2],
    [3, 4, 3]
];
 
// Function Call
countDistinctShortestPaths(n, m, edges);

Java

// Java program for the above approach
 
import 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:

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 zambiatek!