1st to Kth shortest path lengths from node 1 to N in given Graph
Given a directed and weighted graph of N nodes and M edges, the task is to find the 1st to Kth shortest path lengths from node 1 to N.
Examples:
Input: N = 4, M = 6, K = 3, edges = {{1, 2, 1}, {1, 3, 3}, {2, 3, 2}, {2, 4, 6}, {3, 2, 8}, {3, 4, 1}}
Output: 4 4 7
Explanation: The shortest path length from 1 to N is 4, 2nd shortest length is also 4 and 3rd shortest length is 7.Input: N = 3, M = 3, K = 2, edges = {{1, 2, 2}, {2, 3, 2}, {1, 3, 1}}
Output: 1 4
Approach: The idea is to traverse all vertices of the graph using BFS and use priority queue to store the vertices for which the shortest distance is not finalized yet, and also to get the minimum distance vertex. Follow the steps below for the approach.
- Initialize a priority queue, say, pq of size N to store the vertex number and distance value.
- Initialize a 2-d vector, say, dis of size N*K and initialize all values with a very large number, say, 1e9.
- Set dis[1][0] to zero, the distance value of the source vertex.
- Iterate while pq is not empty.
- Pop the value from pq, and store the vertex value in variable u and vertex distance in variable d.
- If d is greater than the distance u, then continue.
- For every adjacent vertex v of u check if the Kth distance value is more than the weight of u-v plus the distance value of u, then update the Kth distance value of v and sort the k distances of vertex v.
Below is the implementation of the above approach:
C++14
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to find K shortest path lengths void findKShortest( int edges[][3], int n, int m, int k) { // Initialize graph vector<vector<pair< int , int > > > g(n + 1); for ( int i = 0; i < m; i++) { // Storing edges g[edges[i][0]].push_back( { edges[i][1], edges[i][2] }); } // Vector to store distances vector<vector< int > > dis(n + 1, vector< int >(k, 1e9)); // Initialization of priority queue priority_queue<pair< int , int >, vector<pair< int , int > >, greater<pair< int , int > > > pq; pq.push({ 0, 1 }); dis[1][0] = 0; // while pq has elements while (!pq.empty()) { // Storing the node value int u = pq.top().second; // Storing the distance value int d = (pq.top().first); pq.pop(); if (dis[u][k - 1] < d) continue ; vector<pair< int , int > > v = g[u]; // Traversing the adjacency list for ( int i = 0; i < v.size(); i++) { int dest = v[i].first; int cost = v[i].second; // Checking for the cost if (d + cost < dis[dest][k - 1]) { dis[dest][k - 1] = d + cost; // Sorting the distances sort(dis[dest].begin(), dis[dest].end()); // Pushing elements to priority queue pq.push({ (d + cost), dest }); } } } // Printing K shortest paths for ( int i = 0; i < k; i++) { cout << dis[n][i] << " " ; } } // Driver Code int main() { // Given Input int N = 4, M = 6, K = 3; int edges[][3] = { { 1, 2, 1 }, { 1, 3, 3 }, { 2, 3, 2 }, { 2, 4, 6 }, { 3, 2, 8 }, { 3, 4, 1 } }; // Function Call findKShortest(edges, N, M, K); return 0; } |
Python3
import heapq def findKShortest(edges, n, m, k): # Initialize graph g = [[] for _ in range (n + 1 )] for i in range (m): # Storing edges g[edges[i][ 0 ]].append((edges[i][ 1 ], edges[i][ 2 ])) # Vector to store distances dis = [[ 1e9 for _ in range (k)] for __ in range (n + 1 )] # Initialization of priority queue pq = [] heapq.heappush(pq, ( 0 , 1 )) dis[ 1 ][ 0 ] = 0 # while pq has elements while pq: # Storing the node value d, u = heapq.heappop(pq) if dis[u][k - 1 ] < d: continue # Traversing the adjacency list for dest, cost in g[u]: # Checking for the cost if d + cost < dis[dest][k - 1 ]: dis[dest][k - 1 ] = d + cost # Sorting the distances dis[dest].sort() # Pushing elements to priority queue heapq.heappush(pq, (d + cost, dest)) # Printing K shortest paths print ( * dis[n][:k]) # Given Input N, M, K = 4 , 6 , 3 edges = [( 1 , 2 , 1 ), ( 1 , 3 , 3 ), ( 2 , 3 , 2 ), ( 2 , 4 , 6 ), ( 3 , 2 , 8 ), ( 3 , 4 , 1 )] # Function Call findKShortest(edges, N, M, K) |
Javascript
<script> // Javascript implementation of above approach // Function to find K shortest path lengths function findKShortest(edges, n, m, k) { // Initialize graph var g = Array.from(Array(n + 1), ()=> new Array()); for ( var i = 0; i < m; i++) { // Storing edges g[edges[i][0]].push([edges[i][1], edges[i][2]]); } // Vector to store distances var dis = Array.from(Array(n+1), ()=> Array(k).fill(1000000000)); // Initialization of priority queue var pq = []; pq.push([0, 1]); dis[1][0] = 0; // while pq has elements while (pq.length != 0) { // Storing the node value var u = pq[pq.length-1][1]; // Storing the distance value var d = (pq[pq.length-1][0]); pq.pop(); if (dis[u][k - 1] < d) continue ; var v = g[u]; // Traversing the adjacency list for ( var i = 0; i < v.length; i++) { var dest = v[i][0]; var cost = v[i][1]; // Checking for the cost if (d + cost < dis[dest][k - 1]) { dis[dest][k - 1] = d + cost; // Sorting the distances dis[dest].sort((a,b)=>a-b); // Pushing elements to priority queue pq.push([(d + cost), dest ]); pq.sort(); } } } // Printing K shortest paths for ( var i = 0; i < k; i++) { document.write(dis[n][i] + " " ); } } // Driver Code // Given Input var N = 4, M = 6, K = 3; var edges = [ [ 1, 2, 1 ], [ 1, 3, 3 ], [ 2, 3, 2 ], [ 2, 4, 6 ], [ 3, 2, 8 ], [ 3, 4, 1 ] ]; // Function Call findKShortest(edges, N, M, K); // This code is contributed by rrrtnx. </script> |
Java
import java.util.*; public class Main { // Function to find K shortest path lengths static void findKShortest( int [][] edges, int n, int m, int k) { // Initialize graph List<List<Pair<Integer, Integer> > > g = new ArrayList<>(); for ( int i = 0 ; i <= n; i++) { g.add( new ArrayList<>()); } for ( int i = 0 ; i < m; i++) { // Storing edges g.get(edges[i][ 0 ]) .add( new Pair<>(edges[i][ 1 ], edges[i][ 2 ])); } // Vector to store distances List<List<Integer> > dis = new ArrayList<>(); for ( int i = 0 ; i <= n; i++) { dis.add( new ArrayList<>()); for ( int j = 0 ; j < k; j++) { dis.get(i).add(Integer.MAX_VALUE); } } // Initialization of priority queue PriorityQueue<Pair<Integer, Integer> > pq = new PriorityQueue<>( (a, b) -> a.getKey() - b.getKey()); pq.add( new Pair<>( 0 , 1 )); dis.get( 1 ).set( 0 , 0 ); // while pq has elements while (!pq.isEmpty()) { // Storing the node value int u = pq.peek().getValue(); // Storing the distance value int d = pq.peek().getKey(); pq.poll(); if (dis.get(u).get(k - 1 ) < d) continue ; List<Pair<Integer, Integer> > v = g.get(u); // Traversing the adjacency list for ( int i = 0 ; i < v.size(); i++) { int dest = v.get(i).getKey(); int cost = v.get(i).getValue(); // Checking for the cost if (d + cost < dis.get(dest).get(k - 1 )) { dis.get(dest).set(k - 1 , d + cost); // Sorting the distances Collections.sort(dis.get(dest)); // Pushing elements to priority queue pq.add( new Pair<>(d + cost, dest)); } } } // Printing K shortest paths for ( int i = 0 ; i < k; i++) { System.out.print(dis.get(n).get(i) + " " ); } } // Driver Code public static void main(String[] args) { // Given Input int N = 4 , M = 6 , K = 3 ; int [][] edges = { { 1 , 2 , 1 }, { 1 , 3 , 3 }, { 2 , 3 , 2 }, { 2 , 4 , 6 }, { 3 , 2 , 8 }, { 3 , 4 , 1 } }; // Function Call findKShortest(edges, N, M, K); } static class Pair<K, V> { private final K key; private final V value; public Pair(K key, V value) { this .key = key; this .value = value; } public K getKey() { return key; } public V getValue() { return value; } } } // This code is contributed by Akash Jha |
C#
using System; using System.Collections.Generic; using System.Linq; public class ShortestPath { public static void FindKShortest( int [, ] edges, int n, int m, int k) { // Initialize graph List<List<KeyValuePair< int , int > > > g = new List<List<KeyValuePair< int , int > > >(); for ( int i = 0; i <= n; i++) { g.Add( new List<KeyValuePair< int , int > >()); } for ( int i = 0; i < m; i++) { // Storing edges g[edges[i, 0]].Add( new KeyValuePair< int , int >( edges[i, 1], edges[i, 2])); } // Vector to store distances int [][] dis = new int [n + 1][]; for ( int i = 0; i <= n; i++) { dis[i] = Enumerable.Repeat( int .MaxValue, k) .ToArray(); } // Initialization of priority queue var pq = new PriorityQueue<KeyValuePair< int , int > >(); pq.Enqueue( new KeyValuePair< int , int >(0, 1)); dis[1][0] = 0; // while pq has elements while (pq.Count > 0) { // Storing the node value int u = pq.Peek().Value; // Storing the distance value int d = pq.Peek().Key; pq.Dequeue(); if (dis[u][k - 1] < d) continue ; List<KeyValuePair< int , int > > v = g[u]; // Traversing the adjacency list for ( int i = 0; i < v.Count; i++) { int dest = v[i].Key; int cost = v[i].Value; // Checking for the cost if (d + cost < dis[dest][k - 1]) { dis[dest][k - 1] = d + cost; // Sorting the distances Array.Sort(dis[dest]); // Pushing elements to priority queue pq.Enqueue( new KeyValuePair< int , int >( d + cost, dest)); } } } // Printing K shortest paths for ( int i = 0; i < k; i++) { Console.Write(dis[n][i] + " " ); } } static void Main( string [] args) { // Given Input int N = 4, M = 6, K = 3; int [, ] edges = { { 1, 2, 1 }, { 1, 3, 3 }, { 2, 3, 2 }, { 2, 4, 6 }, { 3, 2, 8 }, { 3, 4, 1 } }; // Function Call FindKShortest(edges, N, M, K); Console.ReadKey(); } } // Priority queue implementation public class PriorityQueue<T> where T : IComparable<T> { private List<T> data; public PriorityQueue() { this .data = new List<T>(); } public void Enqueue(T item) { data.Add(item); int ci = data.Count - 1; // child index; start at end while (ci > 0) { int pi = (ci - 1) / 2; // parent index if (data[ci].CompareTo(data[pi]) >= 0) break ; // child item is larger than (or // equal Checking for the cost if (d + cost < dis[dest][k - 1]) { dis[dest][k - 1] = d + cost; // Sorting the distances dis[dest].Sort(); // Pushing elements to priority queue pq.Enqueue( new KeyValuePair< int , int >( d + cost, dest)); } } } } // Printing K shortest paths for ( int i = 0; i < k; i++) { Console.Write(dis[n][i] + " " ); } } // Driver Code static void Main( string [] args) { // Given Input int N = 4, M = 6, K = 3; int [, ] edges = { { 1, 2, 1 }, { 1, 3, 3 }, { 2, 3, 2 }, { 2, 4, 6 }, { 3, 2, 8 }, { 3, 4, 1 } }; // Function Call findKShortest(edges, N, M, K); } } } // This code is contributed by Akash Jha |
4 4 7
Time Complexity: O((N+M)*KlogK)
Auxiliary Space: O(NK)