AllPathsFromSourceToTarget.java

packagecom.thealgorithms.backtracking;

importjava.util.ArrayList;
importjava.util.List;

/**
 * Program description - To find all possible paths from source to destination
 * <a href="https://en.wikipedia.org/wiki/Shortest_path_problem">Wikipedia</a>
 *
 * @author <a href="https://github.com/siddhant2002">Siddhant Swarup Mallick</a>
 */
publicclassAllPathsFromSourceToTarget {

// No. of vertices in graph
privatefinalintv;

// To store the paths from source to destination
staticList<List<Integer>> nm = newArrayList<>();
// adjacency list
privateArrayList<Integer>[] adjList;

// Constructor
publicAllPathsFromSourceToTarget(intvertices) {

// initialise vertex count
this.v = vertices;

// initialise adjacency list
initAdjList();
 }

// utility method to initialise adjacency list
privatevoidinitAdjList() {
adjList = newArrayList[v];

for (inti = 0; i < v; i++) {
adjList[i] = newArrayList<>();
 }
 }

// add edge from u to v
publicvoidaddEdge(intu, intv) {
// Add v to u's list.
adjList[u].add(v);
 }

publicvoidstoreAllPaths(ints, intd) {
boolean[] isVisited = newboolean[v];
ArrayList<Integer> pathList = newArrayList<>();

// add source to path[]
pathList.add(s);
// Call recursive utility
storeAllPathsUtil(s, d, isVisited, pathList);
 }

// A recursive function to print all paths from 'u' to 'd'.
// isVisited[] keeps track of vertices in current path.
// localPathList<> stores actual vertices in the current path
privatevoidstoreAllPathsUtil(Integeru, Integerd, boolean[] isVisited, List<Integer> localPathList) {

if (u.equals(d)) {
nm.add(newArrayList<>(localPathList));
return;
 }

// Mark the current node
isVisited[u] = true;

// Recursion for all the vertices adjacent to current vertex

for (Integeri : adjList[u]) {
if (!isVisited[i]) {
// store current node in path[]
localPathList.add(i);
storeAllPathsUtil(i, d, isVisited, localPathList);

// remove current node in path[]
localPathList.remove(i);
 }
 }

// Mark the current node
isVisited[u] = false;
 }

// Driver program
publicstaticList<List<Integer>> allPathsFromSourceToTarget(intvertices, int[][] a, intsource, intdestination) {
// Create a sample graph
AllPathsFromSourceToTargetg = newAllPathsFromSourceToTarget(vertices);
for (int[] i : a) {
g.addEdge(i[0], i[1]);
// edges are added
 }
g.storeAllPaths(source, destination);
// method call to store all possible paths
returnnm;
// returns all possible paths from source to destination
 }
}