Repository: TheAlgorithms/Java
Pull request #5712 (2024-10-11 04:15:52)

feat: add johnson's algorithm
<!--
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/5712?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 `98.43750%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 62.93%. Comparing base [(`7326ab2`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/7326ab2c121ff7059bd17e5745afa7d70b98d0f0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`78146f5`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/78146f59567a81d3572dabb44ec197489740e892?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/5712?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...ithms/datastructures/graphs/JohnsonsAlgorithm.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5712?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fgraphs%2FJohnsonsAlgorithm.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9ncmFwaHMvSm9obnNvbnNBbGdvcml0aG0uamF2YQ==) | 98.43% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5712?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    #5712      +/-   ##
============================================
+ Coverage     62.77%   62.93%   +0.15%     
- Complexity     4025     4057      +32     
============================================
  Files           565      566       +1     
  Lines         15939    16003      +64     
  Branches       3076     3096      +20     
============================================
+ Hits          10006    10071      +65     
+ Misses         5521     5520       -1     
  Partials        412      412              
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5712?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).

saahil-mahato: @alxkm Please review this. Thanks.

Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithm.java b/src/main/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithm.java
new file mode 100644
index 00000000..76c11f78
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithm.java
@@ -0,0 +1,203 @@
+package com.thealgorithms.datastructures.graphs;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * This class implements Johnson's algorithm for finding all-pairs shortest paths in a weighted,
+ * directed graph that may contain negative edge weights.
+ *
+ * Johnson's algorithm works by using the Bellman-Ford algorithm to compute a transformation of the
+ * input graph that removes all negative weights, allowing Dijkstra's algorithm to be used for
+ * efficient shortest path computations.
+ *
+ * Time Complexity: O(V^2 * log(V) + V*E)
+ * Space Complexity: O(V^2)
+ *
+ * Where V is the number of vertices and E is the number of edges in the graph.
+ *
+ * For more information, please visit {@link https://en.wikipedia.org/wiki/Johnson%27s_algorithm}
+ */
+public final class JohnsonsAlgorithm {
+
+    // Constant representing infinity
+    private static final double INF = Double.POSITIVE_INFINITY;
+
+    /**
+     * A private constructor to hide the implicit public one.
+     */
+    private JohnsonsAlgorithm() {
+    }
+
+    /**
+     * Executes Johnson's algorithm on the given graph.
+     *
+     * @param graph The input graph represented as an adjacency matrix.
+     * @return A 2D array representing the shortest distances between all pairs of vertices.
+     */
+    public static double[][] johnsonAlgorithm(double[][] graph) {
+        int numVertices = graph.length;
+        double[][] edges = convertToEdgeList(graph);
+
+        // Step 1: Add a new vertex and run Bellman-Ford
+        double[] modifiedWeights = bellmanFord(edges, numVertices);
+
+        // Step 2: Reweight the graph
+        double[][] reweightedGraph = reweightGraph(graph, modifiedWeights);
+
+        // Step 3: Run Dijkstra's algorithm for each vertex
+        double[][] shortestDistances = new double[numVertices][numVertices];
+        for (int source = 0; source < numVertices; source++) {
+            shortestDistances[source] = dijkstra(reweightedGraph, source, modifiedWeights);
+        }
+
+        return shortestDistances;
+    }
+
+    /**
+     * Converts the adjacency matrix representation of the graph to an edge list.
+     *
+     * @param graph The input graph as an adjacency matrix.
+     * @return An array of edges, where each edge is represented as [from, to, weight].
+     */
+    public static double[][] convertToEdgeList(double[][] graph) {
+        int numVertices = graph.length;
+        List<double[]> edgeList = new ArrayList<>();
+
+        for (int i = 0; i < numVertices; i++) {
+            for (int j = 0; j < numVertices; j++) {
+                if (i != j && !Double.isInfinite(graph[i][j])) {
+                    // Only add edges that are not self-loops and have a finite weight
+                    edgeList.add(new double[] {i, j, graph[i][j]});
+                }
+            }
+        }
+
+        // Convert the List to a 2D array
+        return edgeList.toArray(new double[0][]);
+    }
+
+    /**
+     * Implements the Bellman-Ford algorithm to compute the shortest paths from a new vertex
+     * to all other vertices. This is used to calculate the weight function h(v) for reweighting.
+     *
+     * @param edges The edge list of the graph.
+     * @param numVertices The number of vertices in the original graph.
+     * @return An array of modified weights for each vertex.
+     */
+    private static double[] bellmanFord(double[][] edges, int numVertices) {
+        double[] dist = new double[numVertices + 1];
+        Arrays.fill(dist, INF);
+        dist[numVertices] = 0; // Distance to the new source vertex is 0
+
+        // Add edges from the new vertex to all original vertices
+        double[][] allEdges = Arrays.copyOf(edges, edges.length + numVertices);
+        for (int i = 0; i < numVertices; i++) {
+            allEdges[edges.length + i] = new double[] {numVertices, i, 0};
+        }
+
+        // Relax all edges V times
+        for (int i = 0; i < numVertices; i++) {
+            for (double[] edge : allEdges) {
+                int u = (int) edge[0];
+                int v = (int) edge[1];
+                double weight = edge[2];
+                if (dist[u] != INF && dist[u] + weight < dist[v]) {
+                    dist[v] = dist[u] + weight;
+                }
+            }
+        }
+
+        // Check for negative weight cycles
+        for (double[] edge : allEdges) {
+            int u = (int) edge[0];
+            int v = (int) edge[1];
+            double weight = edge[2];
+            if (dist[u] + weight < dist[v]) {
+                throw new IllegalArgumentException("Graph contains a negative weight cycle");
+            }
+        }
+
+        return Arrays.copyOf(dist, numVertices);
+    }
+
+    /**
+     * Reweights the graph using the modified weights computed by Bellman-Ford.
+     *
+     * @param graph The original graph.
+     * @param modifiedWeights The modified weights from Bellman-Ford.
+     * @return The reweighted graph.
+     */
+    public static double[][] reweightGraph(double[][] graph, double[] modifiedWeights) {
+        int numVertices = graph.length;
+        double[][] reweightedGraph = new double[numVertices][numVertices];
+
+        for (int i = 0; i < numVertices; i++) {
+            for (int j = 0; j < numVertices; j++) {
+                if (graph[i][j] != 0) {
+                    // New weight = original weight + h(u) - h(v)
+                    reweightedGraph[i][j] = graph[i][j] + modifiedWeights[i] - modifiedWeights[j];
+                }
+            }
+        }
+
+        return reweightedGraph;
+    }
+
+    /**
+     * Implements Dijkstra's algorithm for finding shortest paths from a source vertex.
+     *
+     * @param reweightedGraph The reweighted graph to run Dijkstra's on.
+     * @param source The source vertex.
+     * @param modifiedWeights The modified weights from Bellman-Ford.
+     * @return An array of shortest distances from the source to all other vertices.
+     */
+    public static double[] dijkstra(double[][] reweightedGraph, int source, double[] modifiedWeights) {
+        int numVertices = reweightedGraph.length;
+        double[] dist = new double[numVertices];
+        boolean[] visited = new boolean[numVertices];
+        Arrays.fill(dist, INF);
+        dist[source] = 0;
+
+        for (int count = 0; count < numVertices - 1; count++) {
+            int u = minDistance(dist, visited);
+            visited[u] = true;
+
+            for (int v = 0; v < numVertices; v++) {
+                if (!visited[v] && reweightedGraph[u][v] != 0 && dist[u] != INF && dist[u] + reweightedGraph[u][v] < dist[v]) {
+                    dist[v] = dist[u] + reweightedGraph[u][v];
+                }
+            }
+        }
+
+        // Adjust distances back to the original graph weights
+        for (int i = 0; i < numVertices; i++) {
+            if (dist[i] != INF) {
+                dist[i] = dist[i] - modifiedWeights[source] + modifiedWeights[i];
+            }
+        }
+
+        return dist;
+    }
+
+    /**
+     * Finds the vertex with the minimum distance value from the set of vertices
+     * not yet included in the shortest path tree.
+     *
+     * @param dist Array of distances.
+     * @param visited Array of visited vertices.
+     * @return The index of the vertex with minimum distance.
+     */
+    public static int minDistance(double[] dist, boolean[] visited) {
+        double min = INF;
+        int minIndex = -1;
+        for (int v = 0; v < dist.length; v++) {
+            if (!visited[v] && dist[v] <= min) {
+                min = dist[v];
+                minIndex = v;
+            }
+        }
+        return minIndex;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithmTest.java b/src/test/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithmTest.java
new file mode 100644
index 00000000..0ae837cd
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/graphs/JohnsonsAlgorithmTest.java
@@ -0,0 +1,136 @@
+package com.thealgorithms.datastructures.graphs;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import org.junit.jupiter.api.Test;
+
+/**
+ * Unit tests for {@link JohnsonsAlgorithm} class. This class
+ * contains test cases to verify the correct implementation of
+ * various methods used in Johnson's Algorithm such as shortest path
+ * calculations, graph reweighting, and more.
+ */
+class JohnsonsAlgorithmTest {
+
+    // Constant representing infinity
+    private static final double INF = Double.POSITIVE_INFINITY;
+
+    /**
+     * Tests the Johnson's Algorithm with a simple graph without negative edges.
+     * Verifies that the algorithm returns the correct shortest path distances.
+     */
+    @Test
+    void testSimpleGraph() {
+        // Test case for a simple graph without negative edges
+        double[][] graph = {{0, 4, INF, INF}, {INF, 0, 1, INF}, {INF, INF, 0, 2}, {INF, INF, INF, 0}};
+
+        double[][] result = JohnsonsAlgorithm.johnsonAlgorithm(graph);
+
+        double[][] expected = {{0, 4, 5, 7}, {INF, 0, 1, 3}, {INF, INF, 0, 2}, {INF, INF, INF, 0}};
+
+        assertArrayEquals(expected, result);
+    }
+
+    /**
+     * Tests Johnson's Algorithm on a graph with negative edges but no
+     * negative weight cycles. Verifies the algorithm handles negative
+     * edge weights correctly.
+     */
+    @Test
+    void testGraphWithNegativeEdges() {
+        // Graph with negative edges but no negative weight cycles
+        double[][] graph = {{0, -1, 4}, {INF, 0, 3}, {INF, INF, 0}};
+
+        double[][] result = JohnsonsAlgorithm.johnsonAlgorithm(graph);
+
+        double[][] expected = {{0, INF, 4}, {INF, 0, 3}, {INF, INF, 0}};
+
+        assertArrayEquals(expected, result);
+    }
+
+    /**
+     * Tests the behavior of Johnson's Algorithm on a graph with a negative
+     * weight cycle. Expects an IllegalArgumentException to be thrown
+     * due to the presence of the cycle.
+     */
+    @Test
+    void testNegativeWeightCycle() {
+        // Graph with a negative weight cycle
+        double[][] graph = {{0, 1, INF}, {INF, 0, -1}, {-1, INF, 0}};
+
+        // Johnson's algorithm should throw an exception when a negative cycle is detected
+        assertThrows(IllegalArgumentException.class, () -> { JohnsonsAlgorithm.johnsonAlgorithm(graph); });
+    }
+
+    /**
+     * Tests Dijkstra's algorithm as a part of Johnson's algorithm implementation
+     * on a small graph. Verifies that the shortest path is correctly calculated.
+     */
+    @Test
+    void testDijkstra() {
+        // Testing Dijkstra's algorithm with a small graph
+        double[][] graph = {{0, 1, 2}, {INF, 0, 3}, {INF, INF, 0}};
+
+        double[] modifiedWeights = {0, 0, 0}; // No reweighting in this simple case
+
+        double[] result = JohnsonsAlgorithm.dijkstra(graph, 0, modifiedWeights);
+        double[] expected = {0, 1, 2};
+
+        assertArrayEquals(expected, result);
+    }
+
+    /**
+     * Tests the conversion of an adjacency matrix to an edge list.
+     * Verifies that the conversion process generates the correct edge list.
+     */
+    @Test
+    void testEdgeListConversion() {
+        // Test the conversion of adjacency matrix to edge list
+        double[][] graph = {{0, 5, INF}, {INF, 0, 2}, {INF, INF, 0}};
+
+        // Running convertToEdgeList
+        double[][] edges = JohnsonsAlgorithm.convertToEdgeList(graph);
+
+        // Expected edge list: (0 -> 1, weight 5), (1 -> 2, weight 2)
+        double[][] expected = {{0, 1, 5}, {1, 2, 2}};
+
+        // Verify the edge list matches the expected values
+        assertArrayEquals(expected, edges);
+    }
+
+    /**
+     * Tests the reweighting of a graph as a part of Johnson's Algorithm.
+     * Verifies that the reweighted graph produces correct results.
+     */
+    @Test
+    void testReweightGraph() {
+        // Test reweighting of the graph
+        double[][] graph = {{0, 2, 9}, {INF, 0, 1}, {INF, INF, 0}};
+        double[] modifiedWeights = {1, 2, 3}; // Arbitrary weight function
+
+        double[][] reweightedGraph = JohnsonsAlgorithm.reweightGraph(graph, modifiedWeights);
+
+        // Expected reweighted graph:
+        double[][] expected = {{0, 1, 7}, {INF, 0, 0}, {INF, INF, 0}};
+
+        assertArrayEquals(expected, reweightedGraph);
+    }
+
+    /**
+     * Tests the minDistance method used in Dijkstra's algorithm to find
+     * the vertex with the minimum distance that has not yet been visited.
+     */
+    @Test
+    void testMinDistance() {
+        // Test minDistance method
+        double[] dist = {INF, 3, 1, INF};
+        boolean[] visited = {false, false, false, false};
+
+        int minIndex = JohnsonsAlgorithm.minDistance(dist, visited);
+
+        // The vertex with minimum distance is vertex 2 with a distance of 1
+        assertEquals(2, minIndex);
+    }
+}