Class PathSimple

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

Simple Paths in a Graph

Finds ALL simple paths from a source node to a target node using Backtracking. A simple path is a path that does not repeat any nodes.

*

Complexity

Since finding all simple paths between two nodes in a complete graph involves exploring all possible permutations of intermediate nodes, the worst-case time complexity is factorial: O(N!).

  • Field Details

    • log

      protected static final org.slf4j.Logger log

    • n

      protected final int n

    • nodes

      protected final String[] nodes

    • weights

      protected int[][] weights

    • source

      protected int source

    • target

      protected int target

    • mark

      protected boolean[] mark

    • path

      protected int[] path

    • cost

      protected int cost

    • length

      protected int length

    • nsol

      protected int nsol

  • Constructor Details

    • PathSimple

      public PathSimple(int n)

  • Method Details

    • setSource

      public void setSource(int source)

    • setTarget

      public void setTarget(int target)

    • setWeightMatrix

      public void setWeightMatrix(int[][] weights)

    • backtracking

      public void backtracking()

    • backtrack

      protected void backtrack(int current)

    • getPathString

      protected String getPathString(int upToLength)

    • getNumberSolutions

      public int getNumberSolutions()

    • writeWeights

      public String writeWeights()