Yen's Algorithm — K Shortest Paths

Idea

Path k+1 shares prefix with some previous path, then deviates. Try all deviation points, temporarily remove edges to force new path.

Algorithm sketch

List yens(int K, Graph g, int src, int tgt) {
  List result = new ArrayList<>();
  result.add(dijkstra(g, src, tgt));
  for (int k = 1; k < K; k++) {
    // For each node in previous path, try deviating
    // Remove edges of previous same-prefix paths to force deviation
    // Take best new path found
  }
  return result;
}

Complexity

O(K × V × (E + V log V)). Expensive but polynomial.

Eppstein's algorithm

Alternative: O(E + V log V + K) with implicit representation. Complex to implement.