Repository: TheAlgorithms/Java
Pull request #5584 (2024-10-05 14:34:15)

Remove `print` & `main` methods, improve comments, add tests in `Floy…
…dWarshall.java`

<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5584?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `45.45455%` with `6 lines` in your changes missing coverage. Please review.
> Project coverage is 54.68%. Comparing base [(`f34fe4d`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/f34fe4d8408ac35cef900cfae022ffadfc007ea3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`b543f85`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/b543f85f1404697d70a8d52b39457ac43818f4c9?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5584?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...lgorithms/datastructures/graphs/FloydWarshall.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5584?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fgraphs%2FFloydWarshall.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9ncmFwaHMvRmxveWRXYXJzaGFsbC5qYXZh) | 45.45% | [6 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5584?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5584      +/-   ##
============================================
+ Coverage     54.56%   54.68%   +0.12%     
- Complexity     3413     3425      +12     
============================================
  Files           535      535              
  Lines         15383    15385       +2     
  Branches       2935     2934       -1     
============================================
+ Hits           8393     8414      +21     
+ Misses         6637     6616      -21     
- Partials        353      355       +2     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5584?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

Hardvan: I have removed the `main` method as suggested.

Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 7c6f284c..6042dd1b 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -709,6 +709,7 @@
               * [BoruvkaAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/BoruvkaAlgorithmTest.java)
               * [DijkstraAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/DijkstraAlgorithmTest.java)
               * [EdmondsBlossomAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/EdmondsBlossomAlgorithmTest.java)
+              * [FloydWarshallTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/FloydWarshallTest.java)
               * [FordFulkersonTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/FordFulkersonTest.java)
               * [HamiltonianCycleTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/HamiltonianCycleTest.java)
               * [KosarajuTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/graphs/KosarajuTest.java)
diff --git a/src/main/java/com/thealgorithms/datastructures/graphs/FloydWarshall.java b/src/main/java/com/thealgorithms/datastructures/graphs/FloydWarshall.java
index d47ffe3a..66dc6782 100644
--- a/src/main/java/com/thealgorithms/datastructures/graphs/FloydWarshall.java
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/FloydWarshall.java
@@ -1,21 +1,46 @@
 package com.thealgorithms.datastructures.graphs;
 
-import java.util.Scanner;
-
+/**
+ * The {@code FloydWarshall} class provides an implementation of the Floyd-Warshall algorithm
+ * to compute the shortest paths between all pairs of vertices in a weighted graph.
+ * It handles both positive and negative edge weights but does not support negative cycles.
+ * The algorithm is based on dynamic programming and runs in O(V^3) time complexity,
+ * where V is the number of vertices in the graph.
+ *
+ * <p>
+ * The distance matrix is updated iteratively to find the shortest distance between any two vertices
+ * by considering each vertex as an intermediate step.
+ * </p>
+ *
+ * Reference: <a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm">Floyd-Warshall Algorithm</a>
+ */
 public class FloydWarshall {
 
     private int[][] distanceMatrix;
-    private int numberofvertices; // number of vertices in the graph
+    private int numberofvertices;
     public static final int INFINITY = 999;
 
+    /**
+     * Constructs a Floyd-Warshall instance for a graph with the given number of vertices.
+     * Initializes the distance matrix for the graph.
+     *
+     * @param numberofvertices The number of vertices in the graph.
+     */
     public FloydWarshall(int numberofvertices) {
-        distanceMatrix = new int[numberofvertices + 1][numberofvertices + 1]; // stores the value of distance from all the possible path form the source
-        // vertex to destination vertex
+        distanceMatrix = new int[numberofvertices + 1][numberofvertices + 1];
         // The matrix is initialized with 0's by default
         this.numberofvertices = numberofvertices;
     }
 
-    public void floydwarshall(int[][] adjacencyMatrix) { // calculates all the distances from source to destination vertex
+    /**
+     * Executes the Floyd-Warshall algorithm to compute the shortest path between all pairs of vertices.
+     * It uses an adjacency matrix to calculate the distance matrix by considering each vertex as an intermediate point.
+     *
+     * @param adjacencyMatrix The weighted adjacency matrix representing the graph.
+     *                        A value of 0 means no direct edge between the vertices, except for diagonal elements which are 0 (distance to self).
+     */
+    public void floydwarshall(int[][] adjacencyMatrix) {
+        // Initialize the distance matrix with the adjacency matrix.
         for (int source = 1; source <= numberofvertices; source++) {
             for (int destination = 1; destination <= numberofvertices; destination++) {
                 distanceMatrix[source][destination] = adjacencyMatrix[source][destination];
@@ -24,19 +49,29 @@ public class FloydWarshall {
         for (int intermediate = 1; intermediate <= numberofvertices; intermediate++) {
             for (int source = 1; source <= numberofvertices; source++) {
                 for (int destination = 1; destination <= numberofvertices; destination++) {
-                    if (distanceMatrix[source][intermediate] + distanceMatrix[intermediate][destination] < distanceMatrix[source][destination]) { // calculated distance it get replaced as
-                                                                                                                                                  // new shortest distance // if the new
-                                                                                                                                                  // distance calculated is less then the
-                                                                                                                                                  // earlier shortest
+                    // Update distance if a shorter path through the intermediate vertex exists.
+                    if (distanceMatrix[source][intermediate] + distanceMatrix[intermediate][destination] < distanceMatrix[source][destination]) {
                         distanceMatrix[source][destination] = distanceMatrix[source][intermediate] + distanceMatrix[intermediate][destination];
                     }
                 }
             }
         }
+
+        printDistanceMatrix();
+    }
+
+    /**
+     * Prints the distance matrix representing the shortest paths between all pairs of vertices.
+     * The rows and columns correspond to the source and destination vertices.
+     */
+    private void printDistanceMatrix() {
+        // Print header for vertices
         for (int source = 1; source <= numberofvertices; source++) {
             System.out.print("\t" + source);
         }
         System.out.println();
+
+        // Print the distance matrix
         for (int source = 1; source <= numberofvertices; source++) {
             System.out.print(source + "\t");
             for (int destination = 1; destination <= numberofvertices; destination++) {
@@ -46,27 +81,7 @@ public class FloydWarshall {
         }
     }
 
-    public static void main(String... arg) {
-        Scanner scan = new Scanner(System.in);
-        System.out.println("Enter the number of vertices");
-        int numberOfVertices = scan.nextInt();
-        int[][] adjacencyMatrix = new int[numberOfVertices + 1][numberOfVertices + 1];
-        System.out.println("Enter the Weighted Matrix for the graph");
-        for (int source = 1; source <= numberOfVertices; source++) {
-            for (int destination = 1; destination <= numberOfVertices; destination++) {
-                adjacencyMatrix[source][destination] = scan.nextInt();
-                if (source == destination) {
-                    adjacencyMatrix[source][destination] = 0;
-                    continue;
-                }
-                if (adjacencyMatrix[source][destination] == 0) {
-                    adjacencyMatrix[source][destination] = INFINITY;
-                }
-            }
-        }
-        System.out.println("The Transitive Closure of the Graph");
-        FloydWarshall floydwarshall = new FloydWarshall(numberOfVertices);
-        floydwarshall.floydwarshall(adjacencyMatrix);
-        scan.close();
+    public Object[] getDistanceMatrix() {
+        return distanceMatrix;
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/graphs/FloydWarshallTest.java b/src/test/java/com/thealgorithms/datastructures/graphs/FloydWarshallTest.java
new file mode 100644
index 00000000..7d6a2b23
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/graphs/FloydWarshallTest.java
@@ -0,0 +1,33 @@
+package com.thealgorithms.datastructures.graphs;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import org.junit.jupiter.api.Test;
+
+class FloydWarshallTest {
+
+    @Test
+    void testSmallGraph() {
+        int[][] adjacencyMatrix = {{0, 0, 0, 0}, // Ignored row (0 index)
+            {0, 0, 3, FloydWarshall.INFINITY}, {0, FloydWarshall.INFINITY, 0, 1}, {0, FloydWarshall.INFINITY, FloydWarshall.INFINITY, 0}};
+
+        FloydWarshall fw = new FloydWarshall(3);
+        fw.floydwarshall(adjacencyMatrix);
+
+        int[][] expectedDistanceMatrix = {{0, 0, 0, 0}, {0, 0, 3, 4}, {0, FloydWarshall.INFINITY, 0, 1}, {0, FloydWarshall.INFINITY, FloydWarshall.INFINITY, 0}};
+
+        assertArrayEquals(expectedDistanceMatrix, fw.getDistanceMatrix());
+    }
+
+    @Test
+    void testLargerGraph() {
+        int[][] adjacencyMatrix = {{0, 0, 0, 0, 0}, {0, 0, 1, FloydWarshall.INFINITY, 2}, {0, FloydWarshall.INFINITY, 0, 4, FloydWarshall.INFINITY}, {0, FloydWarshall.INFINITY, FloydWarshall.INFINITY, 0, 3}, {0, FloydWarshall.INFINITY, FloydWarshall.INFINITY, FloydWarshall.INFINITY, 0}};
+
+        FloydWarshall fw = new FloydWarshall(4);
+        fw.floydwarshall(adjacencyMatrix);
+
+        int[][] expectedDistanceMatrix = {{0, 0, 0, 0, 0}, {0, 0, 1, 5, 2}, {0, FloydWarshall.INFINITY, 0, 4, 7}, {0, FloydWarshall.INFINITY, FloydWarshall.INFINITY, 0, 3}, {0, FloydWarshall.INFINITY, FloydWarshall.INFINITY, FloydWarshall.INFINITY, 0}};
+
+        assertArrayEquals(expectedDistanceMatrix, fw.getDistanceMatrix());
+    }
+}