Repository: TheAlgorithms/Java
Pull request #6088 (2024-11-13 13:47:29)

Add optimized version of DijkstraAlgorithm
Speed up Dijkstra Algorithm by using another Dijkstra variant that is generally faster.
<!--
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/6088?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 73.51%. Comparing base [(`b971453`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/b9714537f2006da152b07b11115d77f072eae2b2?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`6576314`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/65763146dc839976f7178e0f4df5bf418dea3730?dropdown=coverage&el=desc&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    #6088   +/-   ##
=========================================
  Coverage     73.51%   73.51%           
+ Complexity     5099     5095    -4     
=========================================
  Files           657      657           
  Lines         17625    17625           
  Branches       3393     3391    -2     
=========================================
  Hits          12957    12957           
  Misses         4166     4166           
  Partials        502      502           
```

</details>

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


Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/graphs/DijkstraOptimizedAlgorithm.java b/src/main/java/com/thealgorithms/datastructures/graphs/DijkstraOptimizedAlgorithm.java
new file mode 100644
index 00000000..a686b808
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/graphs/DijkstraOptimizedAlgorithm.java
@@ -0,0 +1,66 @@
+package com.thealgorithms.datastructures.graphs;
+
+import java.util.Arrays;
+import java.util.Set;
+import java.util.TreeSet;
+import org.apache.commons.lang3.tuple.Pair;
+
+/**
+ * Dijkstra's algorithm for finding the shortest path from a single source vertex to all other vertices in a graph.
+ */
+public class DijkstraOptimizedAlgorithm {
+
+    private final int vertexCount;
+
+    /**
+     * Constructs a Dijkstra object with the given number of vertices.
+     *
+     * @param vertexCount The number of vertices in the graph.
+     */
+    public DijkstraOptimizedAlgorithm(int vertexCount) {
+        this.vertexCount = vertexCount;
+    }
+
+    /**
+     * Executes Dijkstra's algorithm on the provided graph to find the shortest paths from the source vertex to all other vertices.
+     *
+     * The graph is represented as an adjacency matrix where {@code graph[i][j]} represents the weight of the edge from vertex {@code i}
+     * to vertex {@code j}. A value of 0 indicates no edge exists between the vertices.
+     *
+     * @param graph The graph represented as an adjacency matrix.
+     * @param source The source vertex.
+     * @return An array where the value at each index {@code i} represents the shortest distance from the source vertex to vertex {@code i}.
+     * @throws IllegalArgumentException if the source vertex is out of range.
+     */
+    public int[] run(int[][] graph, int source) {
+        if (source < 0 || source >= vertexCount) {
+            throw new IllegalArgumentException("Incorrect source");
+        }
+
+        int[] distances = new int[vertexCount];
+        boolean[] processed = new boolean[vertexCount];
+        Set<Pair<Integer, Integer>> unprocessed = new TreeSet<>();
+
+        Arrays.fill(distances, Integer.MAX_VALUE);
+        Arrays.fill(processed, false);
+        distances[source] = 0;
+        unprocessed.add(Pair.of(0, source));
+
+        while (!unprocessed.isEmpty()) {
+            Pair<Integer, Integer> distanceAndU = unprocessed.iterator().next();
+            unprocessed.remove(distanceAndU);
+            int u = distanceAndU.getRight();
+            processed[u] = true;
+
+            for (int v = 0; v < vertexCount; v++) {
+                if (!processed[v] && graph[u][v] != 0 && distances[u] != Integer.MAX_VALUE && distances[u] + graph[u][v] < distances[v]) {
+                    unprocessed.remove(Pair.of(distances[v], v));
+                    distances[v] = distances[u] + graph[u][v];
+                    unprocessed.add(Pair.of(distances[v], v));
+                }
+            }
+        }
+
+        return distances;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/graphs/DijkstraOptimizedAlgorithmTest.java b/src/test/java/com/thealgorithms/datastructures/graphs/DijkstraOptimizedAlgorithmTest.java
new file mode 100644
index 00000000..bf4e2828
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/graphs/DijkstraOptimizedAlgorithmTest.java
@@ -0,0 +1,64 @@
+package com.thealgorithms.datastructures.graphs;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+public class DijkstraOptimizedAlgorithmTest {
+
+    private DijkstraOptimizedAlgorithm dijkstraOptimizedAlgorithm;
+    private int[][] graph;
+
+    @BeforeEach
+    void setUp() {
+        graph = new int[][] {
+            {0, 4, 0, 0, 0, 0, 0, 8, 0},
+            {4, 0, 8, 0, 0, 0, 0, 11, 0},
+            {0, 8, 0, 7, 0, 4, 0, 0, 2},
+            {0, 0, 7, 0, 9, 14, 0, 0, 0},
+            {0, 0, 0, 9, 0, 10, 0, 0, 0},
+            {0, 0, 4, 14, 10, 0, 2, 0, 0},
+            {0, 0, 0, 0, 0, 2, 0, 1, 6},
+            {8, 11, 0, 0, 0, 0, 1, 0, 7},
+            {0, 0, 2, 0, 0, 0, 6, 7, 0},
+        };
+
+        dijkstraOptimizedAlgorithm = new DijkstraOptimizedAlgorithm(graph.length);
+    }
+
+    @Test
+    void testRunAlgorithm() {
+        int[] expectedDistances = {0, 4, 12, 19, 21, 11, 9, 8, 14};
+        assertArrayEquals(expectedDistances, dijkstraOptimizedAlgorithm.run(graph, 0));
+    }
+
+    @Test
+    void testGraphWithDisconnectedNodes() {
+        int[][] disconnectedGraph = {
+            {0, 3, 0, 0}, {3, 0, 1, 0}, {0, 1, 0, 0}, {0, 0, 0, 0} // Node 3 is disconnected
+        };
+
+        DijkstraOptimizedAlgorithm dijkstraDisconnected = new DijkstraOptimizedAlgorithm(disconnectedGraph.length);
+
+        // Testing from vertex 0
+        int[] expectedDistances = {0, 3, 4, Integer.MAX_VALUE}; // Node 3 is unreachable
+        assertArrayEquals(expectedDistances, dijkstraDisconnected.run(disconnectedGraph, 0));
+    }
+
+    @Test
+    void testSingleVertexGraph() {
+        int[][] singleVertexGraph = {{0}};
+        DijkstraOptimizedAlgorithm dijkstraSingleVertex = new DijkstraOptimizedAlgorithm(1);
+
+        int[] expectedDistances = {0}; // The only vertex's distance to itself is 0
+        assertArrayEquals(expectedDistances, dijkstraSingleVertex.run(singleVertexGraph, 0));
+    }
+
+    @Test
+    void testInvalidSourceVertex() {
+        assertThrows(IllegalArgumentException.class, () -> dijkstraOptimizedAlgorithm.run(graph, -1));
+        assertThrows(IllegalArgumentException.class, () -> dijkstraOptimizedAlgorithm.run(graph, graph.length));
+    }
+}