Class PathWorst

java.lang.Object
topics.backtracking.paths.PathSimple
topics.backtracking.paths.PathWorst
public class PathWorst extends PathSimple

Longest Simple Path

Calculates the highest cost simple path (the worst path) from source to target.

*

Pedagogical Note

Finding the longest simple path in a graph with positive weights is an NP-Hard problem. Unlike the shortest path, we cannot easily prune branches here (Branch invalid input: '&' Bound) because we never know if a currently "cheap" path might suddenly encounter a massive weight edge further down the tree. Therefore, we are forced to exhaustively evaluate O(N!) combinations.

  • Field Details

    • worstPath

      protected final int[] worstPath

    • worstCost

      protected int worstCost

    • worstLength

      protected int worstLength

  • Constructor Details

    • PathWorst

      public PathWorst(int n)

  • Method Details

    • backtrack

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

    • getWorstCost

      public int getWorstCost()

    • getWorstPath

      public String getWorstPath()