Class PathBest

java.lang.Object
topics.backtracking.paths.PathSimple
topics.backtracking.paths.PathBest
Direct Known Subclasses:
PathBestPruning
public class PathBest extends PathSimple

Shortest Simple Path (Un-pruned)

Extends the basic pathfinder to track and store the absolute lowest cost path.

*

Pedagogical Note

This problem (Shortest Path) is NOT NP-Hard. It can be solved in polynomial time using algorithms like Dijkstra (Greedy) or Floyd-Warshall (Dynamic Programming). We solve it here using Backtracking purely for educational comparative purposes.

  • Field Details

    • bestPath

      protected final int[] bestPath

    • bestCost

      protected int bestCost

    • bestLength

      protected int bestLength

  • Constructor Details

    • PathBest

      public PathBest(int n)

  • Method Details

    • backtrack

      protected void backtrack(int current)
      Overrides:
      backtrack in class PathSimple

    • getBestCost

      public int getBestCost()

    • getBestPath

      public String getBestPath()