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

public class floyd {

public static final int INF = Integer.MAX_VALUE / 2;

// Function to reconstruct and print the shortest path from u to v
private static void printPath(int u, int v, int[][] next, PrintWriter writer) {
if (next[u][v] == -1) {
writer.println(“No path”);
return;
}
StringBuilder path = new StringBuilder(“V” + (u + 1));
while (u != v) {
u = next[u][v];
path.append(" V").append(u + 1);
}
writer.print(path.toString());
}

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

String inputFile = args[0];
Scanner scanner = new Scanner(new File(inputFile));
PrintWriter writer = new PrintWriter(“output.txt”);

while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (line.startsWith(“Problem”) && line.contains(“n =”)) {
String problemId = line.split(" “)[1]; // Corrected to store the ID correctly
int n = Integer.parseInt(line.split(“n =”)[1].trim());

int[][] dist = new int[n][n];
int[][] next = new int[n][n];

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) dist[i][j] = 0;
else dist[i][j] = INF;
next[i][j] = -1;
}
}

for (int i = 0; i < n; i++) {
if (scanner.hasNextLine()) {
line = scanner.nextLine().trim();
String[] parts = line.split(”\s+“);
for (int j = 0; j < n; j++) {
int val = Integer.parseInt(parts[j]);
if (val != 0) {
dist[i][j] = val;
next[i][j] = j;
}
}
}
}

for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist[i][k] < INF && dist[k][j] < INF && dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
}
}
}
}

writer.println(problemId + “: n = " + n);

// Printing paths and distances
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && dist[i][j] != INF) {
writer.print(problemId + " V” + (i + 1) + “-V” + (j + 1) + “: shortest path and length\n”);
printPath(i, j, next, writer);
writer.println(”: " + dist[i][j]);
}
}
}
}
}
scanner.close();
writer.close();
}
} 

Input 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 

graphfile.txt is the name of a file that includes input. The linesthat correspond to problem j will contains an integer n (between 5 and 10) that indicates how many cities and n x n adjacency matrix A (that is, the distance between n cities, between 1 to 10), in the next n 
rows. Note that no infinity will appear in the matrix A.

The correct and expected 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 

Output the solution of problem 1 first, then problem 2, and etc. The solution of problem j should start with an integer n (the number cities) and the n x n Pointer Array P (in the next n rows). The shortest paths should then follow, one per line. Output the shortest paths from C1 to all other cities, then C2 to all other cities, and Cn to all other cities.