int Graph[][] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
        { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
        { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
        { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
        { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

//This copy of the graph is created so that the user can use this code in a loop (not present in this code) without changing the original Graph.
int altGraph[][] = Graph;
//The mpdifications to the original Graph present in the Alternate Graph (altGraph) will be explained later in the code.

int v = Graph[0].length;
boolean visited[] = new boolean[v];
static ArrayList<ArrayList<Integer>>[] allPaths; 
//Data structure to store all possible paths between 2 nodes

static ArrayList<Integer>[] distances;
//Data structure to store total distance or weight of each path between 2 given nodes

static ArrayList<Integer>[] FinalPaths; 
//Data Structure to store the final set of paths that should be chosen

// Constructor to initialise 'v', the number of nodes
public CircuitSwitching()
{
    this.v = v;
    initAdjList();
}

// utility method to initialise adjacency lists
void initAdjList()
{
    int i;
    adjList = new ArrayList[v];
    for (i = 0; i < v; i  )
        adjList[i] = new ArrayList<>();

    allPaths = new ArrayList[n];
    for(i=0; i<n; i  )
        allPaths[i] = new ArrayList<>();

    distances = new ArrayList[n];

    FinalPaths = new ArrayList[n];
    for(i=0; i<n; i  )
        FinalPaths[i] = new ArrayList<>();
}

/* The graph is transferred from a DDA to an Array of ArrayLists.
 * This prevents checking of pairs of nodes that do not have any edge, thus improving speed in the following operations.
 */
public void addEdges()
{
    int n=v;
    for(int i=0; i<n; i  )
        for(int j=0; j<n; j  )
            if(Graph[i][j]>0)
                adjList[i].add(j);
}

/* In the alternate graph, all incoming edges of every Source node and all outgoing edges of every Destination node are eliminated.
 * This reduces the number of edges that the program has to check, thus improving speed and efficiency.
 */
public void AltGraph()
{
    for(int i=0; i<n; i  )
        for(int j=0; j<9; j  )
        {
            altGraph[j][s[i]] = 0;
            altGraph[d[i]][j] = 0;
        }
}

// Parts of this function have been taken from the code for finding All Paths in a Graph, available on "Geeks For Geeks" 
public void getAllPaths(int s, int d)
{
    boolean[] isVisited = new boolean[v];
    ArrayList<Integer> pathList = new ArrayList<>();
    // add source to path[]
    pathList.add(s);
    // Call utility function
    getAllPathsUtil(s, d, isVisited, pathList, 0);
}

// Parts of this function have been taken from the code for finding All Paths in a Graph, available on "Geeks For Geeks" 
private void getAllPathsUtil(Integer u, Integer d, boolean[] isVisited, ArrayList<Integer> localPathList, int distance)
{
    /* An if condition that prevents the checking of some extra paths by terminating the recursion if the destination node is adjacent to the current node.
     * This prevents the checking of some useless paths and saves time.
     * It assumes that the direct edge between any two nodes is the shortest possible path between them.
     * This condition is only useful when all edges have positive weights.
     */
    if(altGraph[u][d]>0)
    {
        localPathList.add(d);
        allPaths[k].add(new ArrayList<>(localPathList));
        distances[k].add(distance   altGraph[u][d]);
        localPathList.remove(d);
        return;
    }
    isVisited[u] = true;
    // This loop having recursion checks the possibility of creating a path between the Source and Destination using every node.
    for (Integer i : adjList[u])
    {
        if (!isVisited[i])
        {
            // store current node in path
            localPathList.add(i);
            distance  = altGraph[u][i];
            getAllPathsUtil(i, d, isVisited, localPathList, distance);
            distance -= altGraph[u][i];
            // remove current node in path
            localPathList.remove(i);
        }
    }
    isVisited[u] = false;
}

//This function uses Bubble Sort to sort the paths between every pair of Source and Destination nodes with respect to total distance/weight.
void sortPaths()
{
    for(int h=0; h<n; h  )
    {    
        int l = allPaths[h].size();
        for (int i = 0; i < l-1; i  )
            for (int j = 0; j < l-i-1; j  )
                if (distances[h].get(j) > distances[h].get(j 1))
                {
                    Collections.swap(allPaths[h], j, j 1);
                    Collections.swap(distances[h], j, j 1);
                }
    }
}

//This function prints all the paths between every pair of Source and Destination nodes and their respective total distances. 
public void printPaths()
{
    for(int i=0; i<n; i  )
    {
        System.out.println("\nAll paths from "   s[i]   " to "   d[i]   " are:");
        System.out.println("\tDistance\tPaths");
        for(int j=0; j<allPaths[i].size(); j  )
            System.out.println("\t   "   distances[i].get(j)   "\t\t"   allPaths[i].get(j));
    }
}

/* This is the function where the Dynamic Programming takes place.
 * This function iterates through all possible combinations of paths.
 * It returns the combination in which the Longest path is the smallest as compared to the Longest Paths in other combinations.
 * Other conditions, such as Smallest Mean, Smallest Median or other statistical values using all paths in a combination, can also be used as required.
 * The program will have to be modified to accomodate other or more conditions.
 * The purpose of this function is to find the most optimal combination of paths as per the set condition for optimality.
 */
void AltPaths(int p, int max, ArrayList<Integer>[] finalPath)
{
    if(p==n)
    {
        // This is the if statement that finalises the combination based on the set condition.
        if(min>max)
        {
            System.out.println();
            min = max;
            finalise(finalPath);
            System.out.println(finalPath);
        }
        return;
    }
    int i, j, l = allPaths[p].size();
    //This loop recursively creates all combinations of paths to ultimately check the optimality condition.
    for(i=0; i<l; i  )
    {
        if(checkIntersect(allPaths[p].get(i)))
            continue;
        visit(allPaths[p].get(i), p);
        max = Math.max(max, distances[p].get(i));
        finalPath[p] = new ArrayList<>();
        finalPath[p] = allPaths[p].get(i);
        AltPaths(p 1, max, finalPath);
        unvisit(finalPath[p], p);
        finalPath[p].clear();
    }
}

//This function checks if any node in the selected path is already present in a previously selected path.
boolean checkIntersect(ArrayList<Integer> path)
{
    for(int i=1; i<path.size()-1; i  )
        if(visited[path.get(i)])
            return true;
    return false;
}

// This functions visits all nodes in a path so that they can be checked for intersection of another path.
void visit(ArrayList<Integer> path, int p)
{
    for(int i=1; i<path.size()-1; i  )
        visited[path.get(i)] = true;
}

// This function 'unvisits' all nodes in a path once that paths is deleted from the current combination.
void unvisit(ArrayList<Integer> path, int p)
{
    for(int i=1; i<path.size()-1; i  )
        visited[path.get(i)] = false;
}

// This function adds the selected combination to a global variable to be accessed later on.
void finalise(ArrayList<Integer>[] finalPath)
{
    for(int i=0; i<n; i  )
        FinalPaths[i] = new ArrayList<>(finalPath[i]);
}

// This funciton prints the finalised combination, and if there is no data then prints the appropriate message.
void printFinal()
{
    System.out.println("Max distance: "   min   "\nFinal list of paths is: ");
    for(int i=0; i<n; i  )
    {
        if(FinalPaths[i].size()==0)
        {
            System.out.println("The given data transfers cannot occur simultaneously.");
            break;
        }
        else
            System.out.println(FinalPaths[i]);
    }
}

// Driver code
// This code was written in BlueJ which does not require the "String[] args" parameter.
// If compiling in another terminal, write as "main(String[] args)".
public static void main()
{
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter no. of paths to travel:");
    n = sc.nextInt();
    s = new int[n];
    d = new int[n];
    ArrayList <Integer>[] finalPath = new ArrayList[n];
    int i, j;
    for(i=0; i<n; i  )
        finalPath[i] = new ArrayList<>();

    CircuitSwitching g = new CircuitSwitching();
    for(i=0; i<n;i  )
    {
        System.out.println("Enter Source "   (i 1)   ":");
        s[i] = sc.nextInt();
        System.out.println("Enter Destination "   (i 1)   ":");
        d[i] = sc.nextInt();
    }
    g.AltGraph();
    g.addEdges();
    for(i=0; i<n; i  )
    {
        k=i;
        distances[i] = new ArrayList<>();
        g.getAllPaths(s[i], d[i]);
    }
    System.out.println("\n\nSorted Paths: ");
    g.sortPaths();
    g.printPaths();
    System.out.println("\n");
    g.AltPaths(0, 0, finalPath);
    g.printFinal();
}