Yens K Shortest Path Algorithm In C++

In the realm of C++, the K-Shortest Path algorithm developed by Yen serves the purpose of identifying the K shortest distinctive routes within a weighted graph from a starting point to a destination. This technique involves a step-by-step process of pinpointing the shortest path, initially established by Dijkstra's algorithm, and then introducing variations to previously identified routes. Each route variation maintains a priority queue to promptly pinpoint the subsequent potential shortest path. The utilization of this approach proves beneficial in scenarios like network routing and logistics where multiple paths are a necessity. Yen's strategy in C++ makes use of suitable data structures like priority queues and vectors to effectively handle paths and their alterations.

Key Concepts:

• ✅ The technique developed by Yen is based on Dijkstra's algorithm, which finds the shortest path between nodes in a weighted graph.
• ✅ After finding out the shortest path, Yen's algorithm iteratively finds additional routes by introducing deviations, avoiding loops or previously discovered paths.
• ✅ K routes: Yen's method does not stop at the initial shortest road; instead, it searches until it finds a total of K distinct shortest pathways.

Steps to be Followed in C++:

When implementing Yen's K-shortest path algorithm in C++ , common libraries (such as the Standard Template Library (STL)) can be used for data structures like vectors (for storing pathways) and priority queues (for efficient pathfinding). For shortest path discovery, the fundamental Dijkstra algorithm can be implemented as a priority queue.

• ✅ Use the shortest path algorithm, for example, Dijkstra's algorithm.
• ✅ Store a number of routes in a data structure .
• ✅ For each route, make variations by changing edges or removing them.
• ✅ Search further until K routes are found.

Work Flow:

• ✅ Find the Shortest Path: The algorithm first finds the shortest path between the source and destination using Dijkstra's algorithm or any other algorithm available for it.
• ✅ Create Deviations: By deliberately obstructing or making changes in portions of the graph , ensure that the paths are different.
• ✅ Path Ranking: It records all of the shortest paths it has found so far and, when it discovers new ones, ranks them from shortest to longest.
• ✅ Continue This Process Until K Paths Are Found: This process continues until K distinct paths are discovered.

Steps to be followed for these algorithm:

• ✅ Initializing and finding the first shortest path: Finding the first shortest path between source node s and destination node t can be done using Dijkstra's method or another algorithm for it. In the list of size K pathways, add this path as the first path P1.
• ✅ Setting up the alternative paths: Create an empty min-heap (priority queue) B that will contain candidate paths. Every potential route should be significantly different from the previously identified routes.
• ✅ Iterative path for finding the K-1 paths: From 2 to K, for every succeeding k: For every node (i) in the current shortest path (P k−1) (apart from the final node (t): Consider the segment between s and i to be the root route. Any edges in the graph that were part of previously discovered paths that share a root is removed temporarily. This avoids the journey from following the previous path for some time. To find a different path (spur path), apply the algorithm once more from node I to node T. To create a full candidate path, the root path is joined with any spur paths that may exist. To save this new candidate path as the potential shortest path, insert it into min-heap B. Terminate the process to quickly if no more new candidate pathways are found.
• ✅ Retrieve the data and storing the shortest path from the heap: Add the shortest path from B (min-heap) to the list of paths then continue until K shortest paths are found.
• ✅ Output for these paths: When either K paths have been found or there are no more paths to extend, return the list of the K shortest paths.
• ✅ Finding the first shortest path between source node s and destination node t can be done using Dijkstra's method or another algorithm for it.
• ✅ In the list of size K pathways, add this path as the first path P1.
• ✅ Create an empty min-heap (priority queue) B that will contain candidate paths. Every potential route should be significantly different from the previously identified routes.
• ✅ For every node (i) in the current shortest path (P k−1) (apart from the final node (t):
• ✅ Consider the segment between s and i to be the root route.
• ✅ Any edges in the graph that were part of previously discovered paths that share a root is removed temporarily. This avoids the journey from following the previous path for some time.
• ✅ To find a different path (spur path), apply the algorithm once more from node I to node T.
• ✅ To create a full candidate path, the root path is joined with any spur paths that may exist.
• ✅ To save this new candidate path as the potential shortest path, insert it into min-heap B.
• ✅ Terminate the process to quickly if no more new candidate pathways are found.
• ✅ Add the shortest path from B (min-heap) to the list of paths then continue until K shortest paths are found.
• ✅ When either K paths have been found or there are no more paths to extend, return the list of the K shortest paths.

Algorithm:

• ✅ The graph G(V,E) consists of vertices V, edges E, starting node s, and ending node t.
• ✅ A whole number K is employed to indicate the number of shortest paths needed.
• ✅ These represent the K most efficient routes from the starting point S to the destination T.

Pseudo Code:

function yenKShortestPaths(Graph G, Node s, Node t, int K):
    // Step 1: Find the initial shortest path (P1)
    P1 = Dijkstra(G, s, t)
    if P1 is empty:
        return [] // No path found from s to t
    
    paths = [P1] // List to store up to K shortest paths
    B = MinHeap() // Min-heap for candidate paths
    
    // Step 2: Find the next K-1 shortest paths
    for k = 2 to K do:
        for i = 1 to len(paths[k-1]) - 1 do:
            spurNode = paths[k-1][i]
            rootPath = paths[k-1][0:i] // Get the root of the path
            
            // Temporarily remove edges in the graph that follow this root path
            for each path in paths do:
                if rootPath == path[0:i]:
                    removeEdge(path[i], path[i+1])
            
            // Compute the spur path from spurNode to t
            spurPath = Dijkstra(G, spurNode, t)
            
            if spurPath is not empty:
                // Combine root and spur paths to form the full candidate path
                candidatePath = rootPath + spurPath
                B.insert(candidatePath) // Insert candidate path into the min-heap
        
        // Select the shortest path from the heap B and add to paths
        if B is not empty:
            nextShortestPath = B.extractMin()
            paths.append(nextShortestPath)
        else:
            break // No more unique paths can be found, exit loop
    
    return paths // Return up to K shortest paths

Explanation:

• ✅ The Dijkstra's Shortest Path Algorithm is used to compute spur pathways and determine the initial shortest path.
• ✅ Deviation Points: Every node on a path might be the beginning of a different path therefore every deviation creates a new one.
• ✅ Min-Heap for Candidates: It effectively saves and retrieves candidate pathways in ascending path length order.

Time Complexity:

When n represents the quantity of nodes, m denotes the quantity of edges, and K signifies the quantity of required shortest paths, the time complexity is roughly O(K⋅n⋅(m+nlogn)).

Advantages:

Several benefits of the Yen's K-shortest Path Algorithm include:

• ✅ Versatility: It enables the identification of multiple routes, particularly valuable in systems that are subject to frequent changes like networks.
• ✅ Optimization: Yen's approach optimizes the extension of existing paths rather than starting the computations anew.

Example:

Let's consider a scenario to demonstrate the Yen's K-shortest Path Algorithm using C++.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

// Structure to represent an edge in the graph
struct Edge {
    int destination, weight;
};

// Structure to represent a path and its total weight
struct Path {
    vector<int> nodes;
    int totalWeight;

    // Compare paths based on their total weight for the priority queue
    bool operator>(const Path& other) const {
        return totalWeight > other.totalWeight;
    }
};

// Function to run Dijkstra's Algorithm for the shortest path between two nodes
Path dijkstra(const vector<vector<Edge>>& graph, int source, int destination) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    vector<int> prev(n, -1); // To reconstruct the path
    dist[source] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, source});

    while (!pq.empty()) {
        int currentDistance = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        if (currentNode == destination) break;

        for (const auto& edge : graph[currentNode]) {
            int nextNode = edge.destination;
            int weight = edge.weight;

            if (currentDistance + weight < dist[nextNode]) {
                dist[nextNode] = currentDistance + weight;
                prev[nextNode] = currentNode;
                pq.push({dist[nextNode], nextNode});
            }
        }
    }

    Path shortestPath;
    shortestPath.totalWeight = dist[destination];

    if (dist[destination] == INT_MAX) {
        return {}; // No path found
    }

    // Reconstruct path from `prev` array
    for (int at = destination; at != -1; at = prev[at]) {
        shortestPath.nodes.push_back(at);
    }
    reverse(shortestPath.nodes.begin(), shortestPath.nodes.end());

    return shortestPath;
}

// Yen's K-Shortest Paths algorithm
vector<Path> yenKShortestPaths(const vector<vector<Edge>>& graph, int source, int destination, int K) {
    vector<Path> shortestPaths;
    Path firstPath = dijkstra(graph, source, destination);
    if (firstPath.nodes.empty()) return shortestPaths; // No path exists

    shortestPaths.push_back(firstPath);
    priority_queue<Path, vector<Path>, greater<Path>> candidates;

    // Find K-1 alternative paths
    for (int k = 1; k < K; ++k) {
        const Path& lastPath = shortestPaths[k - 1];

        for (int i = 0; i < lastPath.nodes.size() - 1; ++i) {
            int spurNode = lastPath.nodes[i];
            vector<int> rootPath(lastPath.nodes.begin(), lastPath.nodes.begin() + i + 1);

            vector<vector<Edge>> modifiedGraph = graph;

            // Remove edges that are part of previous shortest paths with the same root path
            for (const auto& path : shortestPaths) {
                if (path.nodes.size() > i && vector<int>(path.nodes.begin(), path.nodes.begin() + i + 1) == rootPath) {
                    int from = path.nodes[i];
                    int to = path.nodes[i + 1];
                    modifiedGraph[from].erase(remove_if(modifiedGraph[from].begin(), modifiedGraph[from].end(),
                                                        [to](const Edge& edge) { return edge.destination == to; }),
                                              modifiedGraph[from].end());
                }
            }

            // Find the spur path from spurNode to destination
            Path spurPath = dijkstra(modifiedGraph, spurNode, destination);
            if (!spurPath.nodes.empty()) {
                // Combine rootPath and spurPath to form a new candidate path
                Path totalPath;
                totalPath.nodes = rootPath;
                totalPath.nodes.insert(totalPath.nodes.end(), spurPath.nodes.begin() + 1, spurPath.nodes.end());
                totalPath.totalWeight = firstPath.totalWeight;

                // Insert the new path into the candidates min-heap
                candidates.push(totalPath);
            }
        }

        // If there are no more candidates, break
        if (candidates.empty()) break;

        // Extract the shortest candidate path and add it to the list of shortest paths
        shortestPaths.push_back(candidates.top());
        candidates.pop();
    }

    return shortestPaths;
}

int main() {
    int numNodes = 5;
    vector<vector<Edge>> graph(numNodes);

    // Add edges to the graph
    graph[0].push_back({1, 1});
    graph[0].push_back({2, 1});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 1});
    graph[2].push_back({3, 1});
    graph[3].push_back({4, 1});

    int source = 0;
    int destination = 4;
    int K = 3;

    vector<Path> kShortestPaths = yenKShortestPaths(graph, source, destination, K);

    // Output the K-shortest paths
    cout << "The " << K << " shortest paths from " << source << " to " << destination << " are:\n";
    for (int i = 0; i < kShortestPaths.size(); ++i) {
        cout << "Path " << i + 1 << " (Cost: " << kShortestPaths[i].totalWeight << "): ";
        for (int node : kShortestPaths[i].nodes) {
            cout << node << " ";
        }
        cout << endl;
    }

    return 0;
}

Output:

The 3 shortest paths from 0 to 4 are:
Path 1 (Cost: 3): 0 1 3 4 
Path 2 (Cost: 3): 0 2 3 4 
Path 3 (Cost: 3): 0 1 2 3 4

Conclusion:

In summary, the K-Shortest Path Algorithm developed by Yen offers a systematic approach to discovering multiple distinct routes within a directed network with weighted edges. By leveraging Dijkstra's algorithm for the initial path discovery and introducing deviations to generate diverse paths, Yen's technique can uncover up to K shortest paths connecting a specific source and destination. This method guarantees that each subsequent path differs from its predecessors while maintaining the shortest possible path lengths. Yen's algorithm finds practical use in various fields such as network routing, logistics, and traffic management, providing valuable versatility in situations where alternative routes are advantageous. By employing priority queues and adjacency lists, the C++ implementation of Yen's algorithm stands out for its efficiency and clarity, serving as a valuable asset for addressing intricate pathfinding demands.