In C++, Yen's K-Shortest Path algorithm finds the K shortest unique paths between a source and a destination in a weighted graph. Yen's method iteratively seeks the shortest path (discovered by Dijkstra's algorithm) by producing deviations from the previously determined paths. A priority queue is stored by each path deviation to identify quickly the next possible shortest path. When having multiple paths, the approach can be used, for instance, in network routing and logistics. Yen's method is implemented in C++ using appropriate data structures, such as priority queues and vectors, to manage paths and their deviations efficiently.
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.
- 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.
- 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.
Work Flow:
Steps to be followed for these algorithm:
Algorithm:
Input:
- The graph G(V,E) comprises nodes V, edges E, source node s, and destination node t.
- An integer K is used to specify how many shortest paths are required.
Output:
- These are K shortest paths from S to T.
- 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.
Pseudo Code:
Example
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:
Time Complexity:
Where n is the number of nodes, m is the number of edges, and K is the number of shortest paths needed, the time complexity is approximately O(K⋅n⋅(m+nlogn)).
Advantages:
Several advantages of the Yen's K-shortest Path Algorithm are as follows:
- Flexibility: It allows you to recognize many paths, which is useful in dynamic systems (such as networks) where routes may change.
- Efficiency: Yen's method efficiently expands on established routes rather than recalculating everything from scratch.
Example:
Let us take an example to illustrate the Yen's K-shortest Path Algorithm in C++.
Example
#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:
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 conclusion, the K-Shortest Path Algorithm by Yen is a streamlined technique for identifying several unique paths in a weighted, directed network. Using Dijkstra's algorithm for initial pathfinding and path deviations to produce variations, Yen's method finds up to K shortest paths between a source and a destination. While ensuring that each succeeding path is unique from the ones that preceded it, this approach preserves optimal path lengths. Yen's method finds application in network routing, logistics, and traffic planning, and it provides significant flexibility in scenarios where alternative paths are beneficial. Utilizing priority queues and adjacency lists, Yen's algorithm's C++ implementation is efficient and clear, making it a useful tool for complex pathfinding requirements.