Yen's algorithm for finding the k shortest loopless paths between two nodes.

This algorithm iteratively finds the next shortest path by exploring "spur" deviations from previously found paths. It is a natural extension of Dijkstra's algorithm for applications that require backup routes or alternative paths.

Time Complexity: O(k · N · (E + V log V)) where N is the number of nodes in the shortest path.

Algorithm

1. Find the shortest path using Dijkstra.
2. For each previously found path, consider every node as a "spur node".
3. Temporarily remove the edge following the spur node and all earlier nodes in the path, then run Dijkstra from the spur node to the target.
4. Combine the root path with the spur path to form a candidate.
5. Select the lowest-weight candidate as the next shortest path.

Example

iex> graph = Yog.from_edges(:directed, [
...>     {1, 2, 1}, {1, 3, 2}, {2, 3, 1}, {2, 4, 3},
...>     {3, 4, 1}, {3, 5, 4}, {4, 5, 1}
...>   ])
iex> {:ok, paths} = Yog.Pathfinding.Yen.k_shortest_paths(graph, 1, 5, 3)
iex> length(paths)
3
iex> hd(paths).weight
4

References

• Jin Y. Yen (1971). "Finding the k shortest loopless paths in a network"