Number of shortest paths in an Undirected Weighted Graph
Given a weighted undirected graph G and an integer S, the task is to print the distances of the shortest paths and the count of the number of the shortest paths for each node from a given vertex, S.
Examples:
Input: S =1, G =
Output: Shortest Paths distances are : 0 1 2 4 5 3 2 1 3
Numbers of the shortest Paths are: 1 1 1 2 3 1 1 1 2
Explanation:
- The distance of the shortest paths to vertex 1 is 0 and there is only 1 such path, which is {1}.
- The distance of the shortest paths to vertex 2 is 1 and there is only 1 such path, which is {1?2}.
- The distance of the shortest paths to vertex 3 is 2 and there is only 1 such path, which is {1?2?3}.
- The distance of the shortest paths to vertex 4 is 4 and there exist 2 such paths, which are {{1?2?3?4}, {1?2?3?6?4}}.
- The distance of the shortest paths to vertex 5 is 5 and there exist 3 such paths, which are {{1?2?3?4?5}, {1?2?3?6?4?5}, {1?2?3?6?5}}.
- The distance of the shortest paths to vertex 6 is 3 and there is only 1 such path, which is {1?2?3?6}.
- The distance of the shortest paths to vertex 7 is 2 and there is only 1 such path, which is {1?8?7}.
- The distance of the shortest paths to vertex 8 is 1 and there is only 1 such path, which is {1?8}.
- The distance of the shortest paths to vertex 9 is 3 and there exist 2 such paths, which are {{1?8?9}, {1?2?3?9}}.
Approach: The given problem can be solved using the Dijkstra Algorithm. Follow the steps below to solve the problem:
- Form the adjacency List of the given graph using ArrayList<ArrayList<>> and store it in a variable, say adj.
- Initialize two integers, Arrays say Dist[] and Paths[] all elements as 0 to store the shortest distances of each node and count of paths with the shortest distance from the source Node, S.
- Define a function, say Dijkstra() to find the shortest distances of each node and count the paths with the shortest distance:
- Initialize a min PriorityQueue say PQ and a HashSet of Strings say settled to store if the edge is visited or not.
- Assign 0 to Dist[S] and 1 to Paths[S].
- Now iterate until PQ is not empty() and perform the following operations:
- Find the top Node of the PQ and store the Node value in a variable u.
- Pop the top element of PQ.
- Iterate over the ArrayList adj[u] and perform the following operations
- Store the adjacent node in a variable say to and edge cost in a variable say cost:
- If edge {u, to} is visited, then continue.
- If dist[to] is greater than dist[u]+cost, then assign dist[u]+cost to dist[to] and then assign Paths[u] to Paths[to].
- Otherwise, if dist[to] is equal to dist[u]+cost, then increment Paths[to] by 1.
- Now, Mark, the current edge {u, to} visited in settled.
- Call the function Dijkstra().
- Finally, print the Arrays dist[] and Paths[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Node class class Node { // Stores the node public : // Stores the weight // of the edge int node; int cost; // Constructor Node( int node, int cost) { this ->node = node; this ->cost = cost; } // Costume comparator bool operator<( const Node &n2) const { return cost > n2.cost; } }; // Function to insert a node // in adjacency list void addEdge(vector<vector<Node> > &adj, int x, int y, int w) { adj[x].push_back(Node(y, w)); adj[y].push_back(Node(x, w)); } // Auxiliary function to find shortest paths using // Dijekstra void dijkstra(vector<vector<Node> > &adj, int src, int n, int dist[], int paths[]) { priority_queue<Node> pq; // Stores if a vertex has been visited or not set<pair< int , int > > settled; pq.push(Node(src, 0)); dist[src] = 0; paths[src] = 1; while (!pq.empty()) { // Stores the distance // of node u from s int u = pq.top().node; int d = pq.top().cost; pq.pop(); for ( int i = 0; i < adj[u].size(); i++) { int to = adj[u][i].node; int cost = adj[u][i].cost; if (settled.count(make_pair(to, u))) continue ; if (dist[to] > dist[u] + cost) { pq.push(Node(to, d + cost)); dist[to] = dist[u] + cost; paths[to] = paths[u]; } else if (dist[to] == dist[u] + cost) { paths[to] = (paths[to] + paths[u]); } settled.insert(make_pair(to, u)); } } } void findShortestPaths(vector<vector<Node> > &adj, int s, int n) { int dist[n + 5]; int paths[n + 5]; memset (dist, 0x3f, sizeof (dist)); memset (paths, 0, sizeof (paths)); dijkstra(adj, s, n, dist, paths); cout << "Shortest Paths distances are : " ; for ( int i = 1; i <= n; i++) { cout << dist[i] << " " ; } // Function call to find // the shortest paths cout << endl; cout << "Numbers of the shortest Paths are: " ; for ( int i = 1; i <= n; i++) cout << paths[i] << " " ; } int main() { int N = 9, M = 14; vector<vector<Node> > adj(N + 1); addEdge(adj, 1, 2, 1); addEdge(adj, 2, 3, 1); addEdge(adj, 3, 4, 2); addEdge(adj, 4, 5, 1); addEdge(adj, 5, 6, 2); addEdge(adj, 6, 7, 2); addEdge(adj, 7, 8, 1); addEdge(adj, 8, 1, 1); addEdge(adj, 2, 8, 2); addEdge(adj, 3, 9, 1); addEdge(adj, 8, 9, 2); addEdge(adj, 7, 9, 2); addEdge(adj, 3, 6, 1); addEdge(adj, 4, 6, 1); // Function call findShortestPaths(adj, 1, N); } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Node class static class Node implements Comparator<Node> { // Stores the node public int node; // Stores the weight // of the edge public int cost; public Node() {} // Constructor public Node( int node, int cost) { this .node = node; this .cost = cost; } // Costume comparator @Override public int compare(Node node1, Node node2) { if (node1.cost < node2.cost) return - 1 ; if (node1.cost > node2.cost) return 1 ; return 0 ; } } // Function to insert a node // in adjacency list static void addEdge(ArrayList<ArrayList<Node> > adj, int x, int y, int w) { adj.get(x).add( new Node(y, w)); adj.get(y).add( new Node(x, w)); } // Auxiliary function to find shortest paths using // Dijekstra static void dijkstra(ArrayList<ArrayList<Node> > adj, int src, int n, int dist[], int paths[]) { // Stores the distances of every node in shortest // order PriorityQueue<Node> pq = new PriorityQueue<Node>(n + 1 , new Node()); // Stores if a vertex has been visited or not Set<String> settled = new HashSet<String>(); // Adds the source node with 0 distance to pq pq.add( new Node(src, 0 )); dist[src] = 0 ; paths[src] = 1 ; // While pq is not empty() while (!pq.isEmpty()) { // Stores the top node of pq int u = pq.peek().node; // Stores the distance // of node u from s int d = pq.peek().cost; // Pop the top element pq.poll(); for ( int i = 0 ; i < adj.get(u).size(); i++) { int to = adj.get(u).get(i).node; int cost = adj.get(u).get(i).cost; // If edge is marked if (settled.contains(to + " " + u)) continue ; // If dist[to] is greater // than dist[u] + cost if (dist[to] > dist[u] + cost) { // Add the node to the pq pq.add( new Node(to, d + cost)); // Update dist[to] dist[to] = dist[u] + cost; // Update paths[to] paths[to] = paths[u]; } // Otherwise else if (dist[to] == dist[u] + cost) { paths[to] = (paths[to] + paths[u]); } // Mark the edge visited settled.add(to + " " + u); } } } // Function to find the count of shortest path and // distances from source node to every other node static void findShortestPaths(ArrayList<ArrayList<Node> > adj, int s, int n) { // Stores the distances of a // node from source node int [] dist = new int [n + 5 ]; // Stores the count of shortest // paths of a node from // source node int [] paths = new int [n + 5 ]; for ( int i = 0 ; i <= n; i++) dist[i] = Integer.MAX_VALUE; for ( int i = 0 ; i <= n; i++) paths[i] = 0 ; // Function call to find // the shortest paths dijkstra(adj, s, n, dist, paths); System.out.print( "Shortest Paths distances are : " ); for ( int i = 1 ; i <= n; i++) { System.out.print(dist[i] + " " ); } System.out.println(); System.out.print( "Numbers of the shortest Paths are: " ); for ( int i = 1 ; i <= n; i++) System.out.print(paths[i] + " " ); } // Driver Code public static void main(String[] args) { // Input int N = 9 ; int M = 14 ; ArrayList<ArrayList<Node> > adj = new ArrayList<>(); for ( int i = 0 ; i <= N; i++) { adj.add( new ArrayList<Node>()); } addEdge(adj, 1 , 2 , 1 ); addEdge(adj, 2 , 3 , 1 ); addEdge(adj, 3 , 4 , 2 ); addEdge(adj, 4 , 5 , 1 ); addEdge(adj, 5 , 6 , 2 ); addEdge(adj, 6 , 7 , 2 ); addEdge(adj, 7 , 8 , 1 ); addEdge(adj, 8 , 1 , 1 ); addEdge(adj, 2 , 8 , 2 ); addEdge(adj, 3 , 9 , 1 ); addEdge(adj, 8 , 9 , 2 ); addEdge(adj, 7 , 9 , 2 ); addEdge(adj, 3 , 6 , 1 ); addEdge(adj, 4 , 6 , 1 ); // Function call findShortestPaths(adj, 1 , N); } } |
Python3
import heapq import sys # Node class class Node: # Stores the node def __init__( self , node, cost): # Stores the weight of the edge self .node = node self .cost = cost # Custom comparator def __lt__( self , other): return self .cost < other.cost # Function to insert a node in adjacency list def addEdge(adj, x, y, w): adj[x].append(Node(y, w)) adj[y].append(Node(x, w)) # Auxiliary function to find shortest paths using Dijkstra def dijkstra(adj, src, n): pq = [] # Stores if a vertex has been visited or not settled = set () # Initializing distance of every vertex as infinity dist = [sys.maxsize] * (n + 1 ) # Initializing number of shortest paths to each vertex as 0 paths = [ 0 ] * (n + 1 ) # Pushing the source vertex into the queue heapq.heappush(pq, Node(src, 0 )) # Setting distance of source vertex to 0 dist[src] = 0 # Setting number of shortest paths to source vertex to 1 paths[src] = 1 while pq: # Stores the distance of node u from s u = heapq.heappop(pq) # If the vertex is already settled, continue with the next iteration if (u.node, u.cost) in settled: continue # Mark the vertex as settled settled.add((u.node, u.cost)) for i in range ( len (adj[u.node])): to = adj[u.node][i].node cost = adj[u.node][i].cost if (to, cost) in settled: continue if dist[to] > dist[u.node] + cost: # Found a new shortest path, so update distance and number of shortest paths dist[to] = dist[u.node] + cost paths[to] = paths[u.node] heapq.heappush(pq, Node(to, dist[to])) elif dist[to] = = dist[u.node] + cost: # Found a new path with the same distance as the previous shortest path, so increment the number of shortest paths paths[to] + = paths[u.node] return dist, paths def findShortestPaths(adj, s, n): # Function call to find the shortest paths dist, paths = dijkstra(adj, s, n) print ( "Shortest paths distances are:" , end = " " ) for i in range ( 1 , n + 1 ): print (dist[i], end = " " ) print ( "\nNumbers of the shortest paths are:" , end = " " ) for i in range ( 1 , n + 1 ): print (paths[i], end = " " ) # Main function if __name__ = = "__main__" : N, M = 9 , 14 adj = [[] for i in range (N + 1 )] addEdge(adj, 1 , 2 , 1 ) addEdge(adj, 2 , 3 , 1 ) addEdge(adj, 3 , 4 , 2 ) addEdge(adj, 4 , 5 , 1 ) addEdge(adj, 5 , 6 , 2 ) addEdge(adj, 6 , 7 , 2 ) addEdge(adj, 7 , 8 , 1 ) addEdge(adj, 8 , 1 , 1 ) addEdge(adj, 2 , 8 , 2 ) addEdge(adj, 3 , 9 , 1 ) addEdge(adj, 8 , 9 , 2 ) addEdge(adj, 7 , 9 , 2 ) addEdge(adj, 3 , 6 , 1 ) addEdge(adj, 4 , 6 , 1 ) # Function call to find the shortest paths findShortestPaths(adj, 1 , N) |
C#
// C# program for the above approach using System; using System.Collections.Generic; // Node class class Node : IComparable<Node> { // Stores the node public int node; // Stores the weight // of the edge public int cost; public Node() {} // Constructor public Node( int node, int cost) { this .node = node; this .cost = cost; } // Costume comparator public int CompareTo(Node node2) { if ( this .cost < node2.cost) return -1; if ( this .cost > node2.cost) return 1; return 0; } } class GFG { // Function to insert a node // in adjacency list static void addEdge(List<List<Node> > adj, int x, int y, int w) { adj[x].Add( new Node(y, w)); adj[y].Add( new Node(x, w)); } // Auxiliary function to find shortest paths using // Dijekstra static void dijkstra(List<List<Node> > adj, int src, int n, int [] dist, int [] paths) { // Stores the distances of every node in shortest // order List<Node> pq = new List<Node>(); for ( int i = 0; i <= n; i++) pq.Add( new Node()); // Stores if a vertex has been visited or not HashSet< string > settled = new HashSet< string >(); // Adds the source node with 0 distance to pq pq.Add( new Node(src, 0)); dist[src] = 0; paths[src] = 1; // While pq is not empty() while (pq.Count != 0) { pq.Sort(); // Stores the top node of pq int u = pq[0].node; // Stores the distance // of node u from s int d = pq[0].cost; // Pop the top element pq.RemoveAt(0); for ( int i = 0; i < adj[u].Count; i++) { int to = adj[u][i].node; int cost = adj[u][i].cost; // If edge is marked if (settled.Contains(to + " " + u)) continue ; // If dist[to] is greater // than dist[u] + cost if (dist[to] > dist[u] + cost) { // Add the node to the pq pq.Add( new Node(to, d + cost)); // Update dist[to] dist[to] = dist[u] + cost; // Update paths[to] paths[to] = paths[u]; } // Otherwise else if (dist[to] == dist[u] + cost) { paths[to] = (paths[to] + paths[u]); } // Mark the edge visited settled.Add(to + " " + u); } } } // Function to find the count of shortest path and // distances from source node to every other node static void findShortestPaths(List<List<Node> > adj, int s, int n) { // Stores the distances of a // node from source node int [] dist = new int [n + 5]; // Stores the count of shortest // paths of a node from // source node int [] paths = new int [n + 5]; for ( int i = 0; i <= n; i++) dist[i] = Int32.MaxValue; for ( int i = 0; i <= n; i++) paths[i] = 0; // Function call to find // the shortest paths dijkstra(adj, s, n, dist, paths); Console.Write( "Shortest Paths distances are : " ); for ( int i = 1; i <= n; i++) { Console.Write(dist[i] + " " ); } Console.WriteLine(); Console.Write( "Numbers of the shortest Paths are: " ); for ( int i = 1; i <= n; i++) Console.Write(paths[i] + " " ); } // Driver Code public static void Main( string [] args) { // Input int N = 9; List<List<Node> > adj = new List<List<Node>>(); for ( int i = 0; i <= N; i++) { adj.Add( new List<Node>()); } addEdge(adj, 1, 2, 1); addEdge(adj, 2, 3, 1); addEdge(adj, 3, 4, 2); addEdge(adj, 4, 5, 1); addEdge(adj, 5, 6, 2); addEdge(adj, 6, 7, 2); addEdge(adj, 7, 8, 1); addEdge(adj, 8, 1, 1); addEdge(adj, 2, 8, 2); addEdge(adj, 3, 9, 1); addEdge(adj, 8, 9, 2); addEdge(adj, 7, 9, 2); addEdge(adj, 3, 6, 1); addEdge(adj, 4, 6, 1); // Function call findShortestPaths(adj, 1, N); } } // This code is contributed by phasing17 |
Javascript
// Node class class Node { // Stores the node constructor(node, cost) { // Stores the weight // of the edge this .node = node; this .cost = cost; } // Costume comparator compareTo(n2) { return this .cost - n2.cost; } } // Function to insert a node in adjacency list function addEdge(adj, x, y, w) { adj[x].push( new Node(y, w)); adj[y].push( new Node(x, w)); } // Auxiliary function to find shortest paths using Dijekstra function dijkstra(adj, src, n, dist, paths) { const pq = new PriorityQueue(); // Stores if a vertex has been visited or not const settled = new Set(); pq.push( new Node(src, 0)); dist[src] = 0; paths[src] = 1; while (!pq.isEmpty()) { // Stores the distance of node u from s const u = pq.top().node; const d = pq.top().cost; pq.pop(); for (let i = 0; i < adj[u].length; i++) { const to = adj[u][i].node; const cost = adj[u][i].cost; if (settled.has(`${to},${u}`)) continue ; if (dist[to] > dist[u] + cost) { pq.push( new Node(to, d + cost)); dist[to] = dist[u] + cost; paths[to] = paths[u]; } else if (dist[to] === dist[u] + cost) { paths[to] += paths[u]; } settled.add(`${to},${u}`); } } } function findShortestPaths(adj, s, n) { const dist = new Array(n + 1).fill(Infinity); const paths = new Array(n + 1).fill(0); dijkstra(adj, s, n, dist, paths); console.log( "Shortest Paths distances are : " + dist.slice(1).join( " " )); // Function call to find the shortest paths console.log( "Numbers of the shortest Paths are: " + paths.slice(1).join( " " )); } class PriorityQueue { constructor() { this .queue = []; } push(node) { this .queue.push(node); this .queue.sort((a, b) => a.compareTo(b)); } top() { return this .queue[0]; } pop() { this .queue.shift(); } isEmpty() { return this .queue.length === 0; } } function main() { const N = 9, M = 14; const adj = Array.from({ length: N + 1 }, () => []); addEdge(adj, 1, 2, 1); addEdge(adj, 2, 3, 1); addEdge(adj, 3, 4, 2); addEdge(adj, 4, 5, 1); addEdge(adj, 5, 6, 2); addEdge(adj, 6, 7, 2); addEdge(adj, 7, 8, 1); addEdge(adj, 8, 1, 1); addEdge(adj, 2, 8, 2); addEdge(adj, 3, 9, 1); addEdge(adj, 8, 9, 2); addEdge(adj, 7, 9, 2); addEdge(adj, 3, 6, 1); addEdge(adj, 4, 6, 1); // Function call findShortestPaths(adj, 1, N); } main(); |
Output:
Shortest Paths distances are : 0 1 2 4 5 3 2 1 3 Numbers of the shortest Paths are: 1 1 1 2 3 1 1 1 2
Time Complexity: O(M + N * log(N))
Auxiliary Space: O(M)