Given a weighted directed graph consisting of N nodes and M edges, the task is to find the first K shortest distances between two nodes A and B. (Assuming there are k distinct routes between nodes A and B).
Example:
Input: A=1 , B=4, K=3, Below is the graph :-
Output: 4 4 7Explanation :
The shortest distances are 1→3→4 (distance 4), 1→2→3→4 (distance 4) and 1→2→4 (distance 7).
Recommended: Characteristics or features of an Algorithm
Approach:
The given problem can be solved by slight modification in Dijkstra’s shortest path algorithm. Instead of storing distance of every node from source we will be storing first k shortest distance of every node from the source node and then we will update the distance for the maximum distance among k distances for a single node. Follow the below steps to solve the above problem :
- Initialize a 2-d array distance[u][k] with a infinite. It represents kth shortest distance of node u from source.
- Create an empty set. Every item of set is a pair (weight, vertex). Weight (or distance) is used used as first item of pair as first item is by default used to compare two pairs.
- Insert source vertex into the set and make its distance[0]=0.
- While Set doesn’t become empty, do following:
- Extract minimum distance vertex from Set. Let the extracted vertex be u and minimum distance is min_dis.
- if distance[u][k-1]<min_dis
- Continue
- Loop through all adjacent of u and do following for every vertex v.
- If distance[v][k-1] > min_dis + weight(u, v)
- Update kth distance of v, i.e., do
- distance[v][k-1] = min_dis + weight(u, v)
- If v is in set, update its distance in set by removing it first, then inserting with new distance
- If v is not in set, then insert it in set with new distance
- sort the distance[v] so that maximum distance comes to k-1th index.
- Update kth distance of v, i.e., do
- Print distance array distance[destination][] to print K shortest paths from source to destination.
Implementation in C++:
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the input Graph vector<pair<int, int> > graph[100001]; // Function to input Edges void add_edge(int u, int v, int w) { graph[u].push_back({ v, w }); } // Function to find the k shortest distances // to each node from the src node using // Dijkstra’s Algorithm void shortest_k_dis(int src, int dst, int N, int K) { // Stores the K shortest distance of // each node form src node int distance[N + 1][K]; //intialize with infinite for (int i = 0; i <= N; i++) { for (int j = 0; j < K; j++) distance[i][j] = INT_MAX; } // Stores the node and currrent // minimum distance in a multiset multiset<pair<int, int>> s; s.insert({ 0, src }); distance[src][0] = 0; // BFS for single source shortest // path algorithm while (!s.empty()) { pair<int, int> cur = *s.begin(); s.erase(s.begin()); // Store the node and weight int node = cur.second; int weight = cur.first; // If maximum distance is already less then current distance if (distance[node][K - 1] < weight) continue; // Traverse the adjacency list // of the node for (auto child : graph[node]) { // If the distance obtained // from parent is less than // the current maximum/(k-1)th // distance stored for child if (distance[child.first][K - 1] > child.second + weight) { distance[child.first][K - 1] = weight + child.second; // insert the next pair // in the s s.insert({ distance[child.first][K - 1], child.first }); //sort the distance[child.first] //so maximum distance comes at index k-1 sort(distance[child.first], distance[child.first] + K); } } } // Print the k minimum distance for destination node for (int i = 0; i < K; i++) cout << distance[dst][i] << " "; } // Driver Code int main() { int N = 4, M = 6, A = 1, B = 4, K = 3; // Create a Graph add_edge(1, 2, 1); add_edge(1, 3, 3); add_edge(2, 3, 2); add_edge(2, 4, 6); add_edge(3, 2, 8); add_edge(3, 4, 1); // Function Call shortest_k_dis(A, B, N, K); return 0; }
Output:
4 4 7
Time Complexity: O(M*K*log(N)*log(K))
Auxiliary Space: O(N*K)
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.