import java.io.*;
import java.util.Scanner;
import java.util.LinkedList;


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++) {
                int weight;
                if (values[j].equals("INF")) {
                    weight = Integer.MAX_VALUE;
                } else {
                    weight = Integer.parseInt(values[j]);
                }
                
                adjMatrix[i][j] = weight;
                pMatrix[i][j] = i; // Initialize predecessor matrix
                
                if (i == j) {
                    adjMatrix[i][j] = 0; // Distance from a node to itself is 0
                }
            }
        }
    }

    private static void calculateShortestPaths() {
        int n = adjMatrix.length;
        // Initialize pMatrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (adjMatrix[i][j] == Integer.MAX_VALUE || i == j) {
                    pMatrix[i][j] = -1; // No path or self-loop
                } else {
                    pMatrix[i][j] = i; // Predecessor initially set to source node
                }
            }
        }
        
        // Calculate shortest paths and update pMatrix
        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) {
                        int newDistance = adjMatrix[i][k] + adjMatrix[k][j];
                        if (newDistance < adjMatrix[i][j]) {
                            adjMatrix[i][j] = newDistance;
                            // Update pMatrix to store the predecessor node in the path
                            pMatrix[i][j] = pMatrix[k][j];
                        }
                    }
                }
            }
        }
    }

    private static void printResult(int problemCount, int n) throws FileNotFoundException {
        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++) {
                    out.print(String.format("%2d ", pMatrix[i][j]));
                }
                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
        } catch (IOException ex) {
            System.err.println("An error occurred while writing to the file: " + ex.getMessage());
        }
    }
    

    private static String getShortestPath(int source, int dest) {
        if (adjMatrix[source][dest] == Integer.MAX_VALUE) {
            return "No path";
        }
    
        // Use a list to construct the path in reverse
        LinkedList<String> pathList = new LinkedList<>();
        int currentNode = dest;
    
        while (currentNode != source) {
            pathList.addFirst("V" + (currentNode + 1));
            currentNode = pMatrix[source][currentNode];
        }
        // Add the source node at the beginning
        pathList.addFirst("V" + (source + 1));
        
        // Join the path list with spaces
        return String.join(" ", pathList);
    }
    

    private static void appendToFile(String output) throws FileNotFoundException {
        try (PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(OUTPUT_FILE, true)))) {
            out.print(output);
        } catch (IOException ex) {
            System.err.println("An error occurred while writing to the file: " + ex.getMessage());
        }
    }
}
 The program is giving Pmatrix in the output as Problem1: n = 7
Pmatrix:
-1  0  0  0  0  0  0 
 1 -1  1  1  1  1  1 
 2  2 -1  2  2  2  2 
 3  3  3 -1  3  3  3 
 4  4  4  4 -1  4  4 
 5  5  5  5  5 -1  5 
 6  6  6  6  6  6 -1  but the correct and expected Pmatrix that the program should give is Problem1: n = 7
Pmatrix: 
0  0  0  6  3  0  6  
0  0  5  0  0  4  0  
0  5  0  0  0  0  5  
6  0  0  0  3  0  6  
3  0  0  3  0  3  0  
0  4  0  0  3  0  0  
6  0  5  6  0  0  0 Understand the logic for the Pmatrix for the expected output and make necessary changes to the code