[FEATURE REQUEST] Add Yen’s K-shortest loopless paths algorithm to Graphs

[SamXop123]

What would you like to Propose?

Proposed Issue:

• [type] New implementation

• [name] Yen’s K-shortest loopless paths algorithm

• [problem statement]

  • Given a directed graph with non-negative edge weights and two vertices src and dst, compute the K shortest simple (loopless) paths from src to dst, ordered by total path cost. If fewer than K loopless paths exist, return all available.

• [why]

  • Extends path-finding beyond a single shortest path (e.g., Dijkstra), enabling alternative routing, analysis, and benchmarking.
  • Complements existing graph algorithms in the repository.

• [proposed API]

List<List<Integer>> YensKShortestPaths.kShortestPaths(int[][] weights, int src, int dst, int k)

• weights[u][v] = -1 means no edge; otherwise a non-negative weight.
• Returns up to K vertex-index paths from src to dst, ordered by cost with deterministic tie-breaking.

Issue details

Issue details:

• [algorithm]

  • Implements Yen’s algorithm:
    • Compute the shortest path using Dijkstra (non-negative weights).
    • For each spur node along the last shortest path:
      • Temporarily remove edges that would reproduce an existing root-path prefix.
      • Run Dijkstra from the spur node to dst with loopless constraint (block prior root nodes except spur).
      • Combine root + spur to form a candidate path and push into a min-heap by cost, tie-broken lexicographically on node sequences.
    • Extract the next best candidate; repeat until K paths are gathered or no candidates remain.

• [inputs/outputs]

  • Inputs:
    • weights: square adjacency matrix; -1 indicates no edge; all existing edges have weight >= 0.
    • src, dst: valid vertex indices in [0, n).
    • k >= 1.
  • Outputs:
    • List<List<Integer>> of up to K loopless paths from src to dst.
    • If no path exists: empty list.
    • If src == dst: first path is [src] with cost 0.

• [constraints/validation]

  • Reject null/non-square matrices.
  • Reject weights < -1.
  • Reject invalid indices.
  • Reject k < 1.

• [complexity]

  • Roughly O(K · (V + E) log V) per spur iteration (depends on Dijkstra impl and graph density).
  • Suitable for small/medium graphs typical of educational codebases.

• [files to add/update]

  • Add src/main/java/com/thealgorithms/graph/YensKShortestPaths.java
  • Add src/test/java/com/thealgorithms/graph/YensKShortestPathsTest.java
  • Update DIRECTORY.md under graph/ to index the new class

• [tests]

  • Basic small directed graph: verify first 3 K-paths and deterministic ordering.
  • K larger than available: should return only existing loopless paths.
  • No path: returns empty list.
  • src == dst: returns [ [src] ] as first path.
  • Negative weight entries (other than -1): throw IllegalArgumentException.

• [style/quality gates]

  • Javadoc includes brief description, input contract, complexity, and reference link.
  • Run clang-format (style=file) and mvn verify (tests, Checkstyle, PMD, SpotBugs).

• [references]

  • Wikipedia: https://en.wikipedia.org/wiki/Yen%27s_algorithm

Additional Information

Additional Information:

• [rationale] K-shortest loopless paths are widely used in routing, backup path planning, and comparative algorithm studies. This fills a gap in the current graph/ package.
• [future enhancements]
  • Adjacency-list variant for performance.
  • Optional return type including path costs (List<Path> with nodes + cost).
  • Support for alternate base shortest-path modules (e.g., Johnson for sparse graphs).
• [compatibility]
  • Keeps consistent matrix-based API used in several existing graph algorithms in this repo.
  • Deterministic tie-breaking (lexicographic on node sequences) ensures stable tests.