import java.io.*;
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;
                } else {
                    int weight = Integer.parseInt(values[j]);
                    adjMatrix[i][j] = weight;
                    if (i != j && weight < Integer.MAX_VALUE) {
                        pMatrix[i][j] = j; // Direct path from i to j, so next hop toward j is j itself
                    } else {
                        pMatrix[i][j] = 0; // No direct path or self
                    }
                }
            }
        }
    }
    
    

    private static void calculateShortestPaths() {
        int n = adjMatrix.length;
    
        // Initialize Pmatrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // Initialize Pmatrix to -1 indicating no path unless there is a direct path
                pMatrix[i][j] = 0;
    
                if (adjMatrix[i][j] != Integer.MAX_VALUE && i != j) {
                    // Direct path from i to j, set next hop to j
                    pMatrix[i][j] = j;
                }
            }
        }
    
        // Floyd-Warshall algorithm
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // Check if path i -> k -> j is shorter than the current i -> j
                    if (adjMatrix[i][k] != Integer.MAX_VALUE && adjMatrix[k][j] != Integer.MAX_VALUE) {
                        long ik_kj_path = ((long) adjMatrix[i][k]) + adjMatrix[k][j];
                        if (ik_kj_path < adjMatrix[i][j]) {
                            adjMatrix[i][j] = (int) ik_kj_path;
                            // Update pMatrix[i][j] to go through intermediate node k
                            pMatrix[i][j] = pMatrix[i][k];
                        }
                    }
                }
            }
        }
    }
    
    

    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";
        }
    
        StringBuilder path = new StringBuilder("V" + (source + 1));
        int next = source;
        // Traverse from source to destination using Pmatrix to construct the path
        while (next != dest) {
            next = pMatrix[next][dest];
            if(next == -1) break; // Break if there’s no valid next step (should not happen in a correctly initialized Pmatrix)
            path.append(" V").append(next + 1);
        }
    
        return path.toString();
    }
    

    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 input for the above program is:

Problem1 Amatrix: n = 7
0  6  5  4  6  3  6  
6  0  6  4  5  5  3  
5  6  0  3  1  4  6  
4  4  3  0  4  1  4  
6  5  1  4  0  5  5  
3  5  4  1  5  0  3  
6  3  6  4  5  3  0  

Problem2 Amatrix: n = 6
0  1  2  1  3  4  
1  0  3  2  2  3  
2  3  0  3  3  6  
1  2  3  0  3  5  
3  2  3  3  0  5  
4  3  6  5  5  0

The output got by running the above program for the above input is:

Problem1: n = 7
Pmatrix:
 0  1  2  3  4  5  6 
 0  0  2  3  4  5  6 
 0  1  0  3  4  5  6 
 0  1  2  0  4  5  6 
 0  1  2  3  0  5  6 
 0  1  2  3  4  0  6 
 0  1  2  3  4  5  0 

V1-Vj: shortest path and length
V1: 0
V1 V2: 6
V1 V3: 5
V1 V4: 4
V1 V5: 6
V1 V6: 3
V1 V7: 6

V2-Vj: shortest path and length
V2 V1: 6
V2: 0
V2 V3: 6
V2 V4: 4
V2 V5: 5
V2 V6: 5
V2 V7: 3

V3-Vj: shortest path and length
V3 V1: 5
V3 V2: 6
V3: 0
V3 V4: 3
V3 V5: 1
V3 V6: 4
V3 V7: 6

V4-Vj: shortest path and length
V4 V1: 4
V4 V2: 4
V4 V3: 3
V4: 0
V4 V5: 4
V4 V6: 1
V4 V7: 4

V5-Vj: shortest path and length
V5 V1: 6
V5 V2: 5
V5 V3: 1
V5 V4: 4
V5: 0
V5 V6: 5
V5 V7: 5

V6-Vj: shortest path and length
V6 V1: 3
V6 V2: 5
V6 V3: 4
V6 V4: 1
V6 V5: 5
V6: 0
V6 V7: 3

V7-Vj: shortest path and length
V7 V1: 6
V7 V2: 3
V7 V3: 6
V7 V4: 4
V7 V5: 5
V7 V6: 3
V7: 0


Problem2: n = 6
Pmatrix:
 0  1  2  3  4  5 
 0  0  2  3  4  5 
 0  1  0  3  4  5 
 0  1  2  0  4  5 
 0  1  2  3  0  5 
 0  1  2  3  4  0 

V1-Vj: shortest path and length
V1: 0
V1 V2: 1
V1 V3: 2
V1 V4: 1
V1 V5: 3
V1 V6: 4

V2-Vj: shortest path and length
V2 V1: 1
V2: 0
V2 V3: 3
V2 V4: 2
V2 V5: 2
V2 V6: 3

V3-Vj: shortest path and length
V3 V1: 2
V3 V2: 3
V3: 0
V3 V4: 3
V3 V5: 3
V3 V6: 6

V4-Vj: shortest path and length
V4 V1: 1
V4 V2: 2
V4 V3: 3
V4: 0
V4 V5: 3
V4 V6: 5

V5-Vj: shortest path and length
V5 V1: 3
V5 V2: 2
V5 V3: 3
V5 V4: 3
V5: 0
V5 V6: 5

V6-Vj: shortest path and length
V6 V1: 4
V6 V2: 3
V6 V3: 6
V6 V4: 5
V6 V5: 5
V6: 0
But this output is incorrectly showing the Pmatrix.

The correct output 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

V1-Vj: shortest path and length
V1 V1: 0
V1 V2: 6
V1 V3: 5
V1 V6 V4: 4
V1 V3 V5: 6
V1 V6: 3
V1 V6 V7: 6

V2-Vj: shortest path and length
V2 V1: 6
V2 V2: 0
V2 V5 V3: 6
V2 V4: 4
V2 V5: 5
V2 V4 V6: 5
V2 V7: 3

V3-Vj: shortest path and length
V3 V1: 5
V3 V5 V2: 6
V3 V3: 0
V3 V4: 3
V3 V5: 1
V3 V6: 4
V3 V5 V7: 6

V4-Vj: shortest path and length
V4 V6 V1: 4
V4 V2: 4
V4 V3: 3
V4 V4: 0
V4 V3 V5: 4
V4 V6: 1
V4 V6 V7: 4

V5-Vj: shortest path and length
V5 V3 V1: 6
V5 V2: 5
V5 V3: 1
V5 V3 V4: 4
V5 V5: 0
V5 V3 V6: 5
V5 V7: 5

V6-Vj: shortest path and length
V6 V1: 3
V6 V4 V2: 5
V6 V3: 4
V6 V4: 1
V6 V3 V5: 5
V6 V6: 0
V6 V7: 3

V7-Vj: shortest path and length
V7 V6 V1: 6
V7 V2: 3
V7 V5 V3: 6
V7 V6 V4: 4
V7 V5: 5
V7 V6: 3
V7 V7: 0

Problem2: n = 6
Pmatrix:
0 0 0 0 2 2
0 0 1 1 0 0
0 1 0 1 0 2
0 1 1 0 0 2
2 0 0 0 0 2
2 0 2 2 2 0

V1-Vj: shortest path and length
V1 V1: 0
V1 V2: 1
V1 V3: 2
V1 V4: 1
V1 V2 V5: 3
V1 V2 V6: 4

V2-Vj: shortest path and length
V2 V1: 1
V2 V2: 0
V2 V1 V3: 3
V2 V1 V4: 2
V2 V5: 2
V2 V6: 3

V3-Vj: shortest path and length
V3 V1: 2
V3 V1 V2: 3
V3 V3: 0
V3 V1 V4: 3
V3 V5: 3
V3 V1 V2 V6: 6

V4-Vj: shortest path and length
V4 V1: 1
V4 V1 V2: 2
V4 V1 V3: 3
V4 V4: 0
V4 V5: 3
V4 V1 V2 V6: 5

V5-Vj: shortest path and length
V5 V2 V1: 3
V5 V2: 2
V5 V3: 3
V5 V4: 3
V5 V5: 0
V5 V2 V6: 5

V6-Vj: shortest path and length
V6 V2 V1: 4
V6 V2: 3
V6 V2 V1 V3: 6
V6 V2 V1 V4: 5
V6 V2 V5: 5
V6 V6: 0 

In the correct output the Pmatrix is correct and the program is expected to print the same Pmatrix. Consider the Problem1: n = 7 of the correct output.
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

V1-Vj: shortest path and length
V1 V1: 0
V1 V2: 6
V1 V3: 5
V1 V6 V4: 4
V1 V3 V5: 6
V1 V6: 3
V1 V6 V7: 6


According to the logic the 1st row of the Pmatrix for Problem1: n = 7 should be like 0 0 0 6 3 0 6 which represents the node on the path from V1 to Vj. For eg. V1 to V1 there is no path so 0 is shown in 1st column of 0 0 0 6 3 0 6. V1 to V2 is directly connected and there is no other shortest path so 0 is shown in 2nd column of 0 0 0 6 3 0 6. V1 to V3 is directly connected and there is no other shortest path so 0 is shown in 3rd column of 0 0 0 6 3 0 6. V1 to V4 there is shortest path through node V6 (V1 V6 V4: 4) so 6 is shown in 4th column of 0 0 0 6 3 0 6. V1 to V5 there is shortest path through node V3 (V1 V3 V5: 6) so 3 is shown in 5th column of 0 0 0 6 3 0 6. V1 to V6 is directly connected and there is no other shortest path so 0 is shown in 6th column of 0 0 0 6 3 0 6. V1 to V7 there is shortest path through node V6 (V1 V6 V7: 6) so 6 is shown in 7th column of 0 0 0 6 3 0 6. This logic should be applied to all other rows to get the correct Pmatrix. Make necessary changes to the code to get the expected output.

Make changes to the code such that it constructs the Pmatrix according to the above described logic.