path(index q, r)
    if (P[ q, r ]!=0)
         path(q, P[q, r])
         println( “v”+ P[q, r])
         path(P[q, r], r)
     return;
//no intermediate nodes
else return
If D[q, r] < infinity, print node q and call path(...), after returning from path(...), print node r. Apply this logic to the Pmatrix in the program import java.io.*;
import java.util.*;
import java.util.Scanner;


public class floyd {
    private static int[][] adjMatrix;
    private static int[][] pMatrix;
    private static final String OUTPUT_FILE = "output.txt";

    public static void main(String[] args) throws IOException {
        if (args.length != 1) {
            System.err.println("Usage: java Floyd <graph-file>");
            return;
        }

        try (Scanner scanner = new Scanner(new BufferedReader(new FileReader(args[0])))) {
            createFile();

            int problemCount = 0;

            while (scanner.hasNextLine()) {
                String line = scanner.nextLine();

                if (line.startsWith("Problem")) {
                    problemCount++;
                    int n = extractNumberOfVertices(line);

                    if (n < 5 || n > 10) {
                        throw new IllegalArgumentException("Invalid number of vertices.");
                    }

                    // Read adjacency matrix for the current problem
                    initializeMatrices(n, scanner);

                    // Compute shortest paths and print results
                    calculateShortestPaths();
                    printResult(problemCount, n);
                }
            }
        }
    }

    private static void createFile() throws FileNotFoundException {
        PrintWriter writer = new PrintWriter(OUTPUT_FILE);
        writer.close();
    }

    private static int extractNumberOfVertices(String line) {
        // Extracts the number of vertices from the line
        String[] parts = line.split("n = ");
        return Integer.parseInt(parts[1].trim());
    }

    private static void initializeMatrices(int n, Scanner scanner) {
        adjMatrix = new int[n][n];
        pMatrix = new int[n][n];
    
        for (int i = 0; i < n; i++) {
            String[] values = scanner.nextLine().trim().split("\s+");
            for (int j = 0; j < n; j++) {
                if (values[j].equals("INF")) {
                    adjMatrix[i][j] = Integer.MAX_VALUE;
                    pMatrix[i][j] = j; // Initialize as destination node itself
                } else {
                    int weight = Integer.parseInt(values[j]);
                    adjMatrix[i][j] = weight;
                    pMatrix[i][j] = i == j ? -1 : 0; // Direct path logic adjusted
                }
            }
        }
    }
    
    
    private static void calculateShortestPaths() {
        int n = adjMatrix.length;
        
        // Initialize pMatrix for direct paths and self-loops
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || adjMatrix[i][j] == Integer.MAX_VALUE) {
                    pMatrix[i][j] = -1; // No path initially
                } else {
                    pMatrix[i][j] = i; // Direct path exists, storing predecessor
                }
            }
        }
    
        // Apply Floyd-Warshall algorithm
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (adjMatrix[i][k] != Integer.MAX_VALUE && adjMatrix[k][j] != Integer.MAX_VALUE) {
                        long newPathDist = (long)adjMatrix[i][k] + adjMatrix[k][j];
                        if (newPathDist < adjMatrix[i][j]) {
                            adjMatrix[i][j] = (int)newPathDist;
                            pMatrix[i][j] = pMatrix[k][j];
                        }
                    }
                }
            }
        }
    }
    
    private static void printResult(int problemCount, int n) throws FileNotFoundException, IOException {
        try (PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(OUTPUT_FILE, true)))) {
            out.println("Problem" + problemCount + ": n = " + n);
            out.println("Pmatrix:");
    
            // Output the pMatrix for the problem
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) {
                        out.print("0 ");
                    } else {
                        // Print the number of the node just before destination on the shortest path
                        out.print((pMatrix[i][j] != -1 ? (pMatrix[i][j] + 1) : "-") + " ");
                    }
                }
                out.println();
            }
    
            out.println();
    
            // Output shortest paths for each city to all other cities
            for (int source = 0; source < n; source++) {
                out.println("V" + (source + 1) + "-Vj: shortest path and length");
                for (int dest = 0; dest < n; dest++) {
                    // Get the shortest path and distance between the source and destination
                    String path = getShortestPath(source, dest);
                    int distance = adjMatrix[source][dest];
                    out.println(path + ": " + distance);
                }
                out.println();
            }
            out.println(); // Separate problems visually
        }
    }
        
    

    private static String getShortestPath(int source, int dest) {
        if (adjMatrix[source][dest] == Integer.MAX_VALUE) {
            return "No path";
        }
    
        List<Integer> path = new ArrayList<>();
        for (int at = dest; at != -1; at = pMatrix[source][at]) {
            path.add(at); // Collect in reverse order
        }
        Collections.reverse(path); // Reverse to get the correct order starting from source
    
        // Build the output
        StringBuilder pathStr = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            if (i > 0) pathStr.append(" ");
            pathStr.append("V").append(path.get(i) + 1); // Add 1 for 1-indexed vertex numbering
        }
    
        return pathStr.toString();
    }
    
}