Write a program floyd.java to find all pairs shortest paths using Floyd’s algorithm for…
- User
Write a program floyd.java to find all pairs shortest paths using Floyd’s algorithm for several undirected complete graphs, which are saved in a file called output.txt. Print all pairs shortest paths and their lengths.
Program Usage Your program should be invoked as follows $> floyd
Graph File: is the name of a file that includes more than one problem. The lines that 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.
A sample graph file appears below. Problem 1: 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
Problem 2: 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
Output File 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.
A sample output file: 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 0V1-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 0V1-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
- Assistant
To solve this problem, we would have to create a Java program
floyd.javathat implements Floyd's Algorithm to find the shortest paths between all pairs of vertices in one or more given graphs. The program should read the graphs from a specified file, calculate the shortest paths and their lengths, and finally, write the results to an output file. Below, you'll find a basic implementation of how you might structure this program:import java.io.*; import java.util.Scanner; public class floyd { 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"); // Process each problem in the file while (scanner.hasNextInt()) { int n = scanner.nextInt(); // Read the number of vertices/cities int[][] dist = new int[n][n]; // Distance matrix int[][] next = new int[n][n]; // Next matrix to reconstruct paths // Initialize matrices for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = scanner.nextInt(); if(dist[i][j] != 0) { next[i][j] = j; } } } // Floyd's Algorithm for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (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("Problem" + ": n = " + n); writer.println("Pmatrix:"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { writer.print(next[i][j] + " "); } writer.println(); } // Reconstructing paths for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) { int u = i; String path = "V" + (i+1); while(u != j){ u = next[u][j]; path += " V" + (u+1); } writer.println("V" + (i+1) + "-V" + (j+1) + ": shortest path and length"); writer.println(path + ": " + dist[i][j]); } } } } scanner.close(); writer.close(); } }Before running this program, ensure your Java development environment is configured correctly and that you have an input file structured according to the specifications you provided.
Please note, this code offers a basic implementation meant to serve as a starting point. Depending on the exact format required and the potential edge cases that might arise from specific input graphs, further adjustments may be necessary. Always extensively test your code with various input examples to ensure the output meets all expected requirements.
- User
I want to execute the above program using ./floyd graphfile.txt. How to do this
- Assistant
To execute a Java program from the command line using a syntax like
./floyd graphfile.txt, you'll have to create a shell script that wraps the Java execution command. This approach is useful when you want to simplify the Java program's execution or make it resemble a native command-line tool.Follow these steps to create and use such a script:
Step 1: Compile Your Java Program
First, compile
floyd.javato produce afloyd.classfile:javac floyd.javaEnsure you have the Java Development Kit (JDK) installed on your system and that the
javaccommand is available in your system's PATH.Step 2: Create a Shell Script
Create a shell script named
floyd(without the.javaextension) in the same directory where yourfloyd.classfile is located. Open a new file in a text editor and add the following lines:#!/bin/bash java floyd $@This script uses the shebang line
#!/bin/bashto tell the system to execute the script with bash. It runs the Java VM withfloydas the main class (hencejava floyd) and forwards all command line arguments ($@) to it.Step 3: Make the Shell Script Executable
You need to make this script executable to run it like a native command. Use the
chmodcommand as follows:chmod +x floydNow, your shell script is executable.
Step 4: (Optional) Add Script to Your PATH
If you want to run the script from any directory (not just where it's located), you should move it to a directory that's on your system's PATH, or add the script's directory to your PATH.
To add the script’s directory to your PATH for the current session, you can use:
export PATH=$PATH:/path/to/your/script/directoryTo make it permanent, add the above line to your
.bashrcor.bash_profilefile in your home directory.Step 5: Run Your Program
Now, you can run your program as intended:
./floyd graphfile.txtThis command will invoke the shell script
floyd, which in turn runs your Java program withgraphfile.txtas its argument, just like a native binary or script.Remember, the shell script and
floyd.classmust be in the same directory for this to work, or you must reference the class with its package name or use the-classpathoption if it's elsewhere.