Find first K shortest distances between two nodes in graph

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 :-

Graph

Output: 4 4 7

Explanation :

The shortest distances are 1→3→4 (distance 4), 1→2→3→4 (distance 4) and 1→2→4 (distance 7).

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.
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.