Repository: TheAlgorithms/Java
Pull request #6205 (2025-03-31 14:38:25)

feat: add Traveling Salesman Problem implementation
<!--
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
-->
The Traveling Salesman Problem (TSP) asks:
"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
TSP is NP-hard and serves as a benchmark for optimization algorithms.
For more information, see <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">Wikipedia</a>.

- Added brute-force solution with permutation generation (O(n!))
- Implemented dynamic programming solution (Held-Karp algorithm, O(n^2*2^n))
- Included comprehensive test cases for both approaches
- Added detailed JavaDoc documentation for all methods

<!-- 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/6205?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 `81.96721%` with `11 lines` in your changes missing coverage. Please review.
> Project coverage is 73.77%. Comparing base [(`4514887`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/45148874e841c3b0db0a5a0d46e2871f30b0d3e0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`88e5f7b`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/88e5f7be2b4f904bc3118abfee364db9152a3315?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/6205?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...ava/com/thealgorithms/graph/TravelingSalesman.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6205?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fgraph%2FTravelingSalesman.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9ncmFwaC9UcmF2ZWxpbmdTYWxlc21hbi5qYXZh) | 81.96% | [5 Missing and 6 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6205?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    #6205      +/-   ##
============================================
+ Coverage     73.75%   73.77%   +0.02%     
- Complexity     5273     5296      +23     
============================================
  Files           669      670       +1     
  Lines         18282    18343      +61     
  Branches       3528     3546      +18     
============================================
+ Hits          13483    13532      +49     
- Misses         4258     4264       +6     
- Partials        541      547       +6     
```

</details>

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

<details><summary> :rocket: New features to boost your workflow: </summary>

- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
</details>

Patch:
diff --git a/src/main/java/com/thealgorithms/graph/TravelingSalesman.java b/src/main/java/com/thealgorithms/graph/TravelingSalesman.java
new file mode 100644
index 00000000..14bf89f5
--- /dev/null
+++ b/src/main/java/com/thealgorithms/graph/TravelingSalesman.java
@@ -0,0 +1,155 @@
+package com.thealgorithms.graph;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * This class provides solutions to the Traveling Salesman Problem (TSP) using both brute-force and dynamic programming approaches.
+ * For more information, see <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">Wikipedia</a>.
+ * @author  <a href="https://github.com/DenizAltunkapan">Deniz Altunkapan</a>
+ */
+
+public final class TravelingSalesman {
+
+    // Private constructor to prevent instantiation
+    private TravelingSalesman() {
+    }
+
+    /**
+     * Solves the Traveling Salesman Problem (TSP) using brute-force approach.
+     * This method generates all possible permutations of cities, calculates the total distance for each route, and returns the shortest distance found.
+     *
+     * @param distanceMatrix A square matrix where element [i][j] represents the distance from city i to city j.
+     * @return The shortest possible route distance visiting all cities exactly once and returning to the starting city.
+     */
+    public static int bruteForce(int[][] distanceMatrix) {
+        if (distanceMatrix.length <= 1) {
+            return 0;
+        }
+
+        List<Integer> cities = new ArrayList<>();
+        for (int i = 1; i < distanceMatrix.length; i++) {
+            cities.add(i);
+        }
+
+        List<List<Integer>> permutations = generatePermutations(cities);
+        int minDistance = Integer.MAX_VALUE;
+
+        for (List<Integer> permutation : permutations) {
+            List<Integer> route = new ArrayList<>();
+            route.add(0);
+            route.addAll(permutation);
+            int currentDistance = calculateDistance(distanceMatrix, route);
+            if (currentDistance < minDistance) {
+                minDistance = currentDistance;
+            }
+        }
+
+        return minDistance;
+    }
+
+    /**
+     * Computes the total distance of a given route.
+     *
+     * @param distanceMatrix A square matrix where element [i][j] represents the
+     *                       distance from city i to city j.
+     * @param route          A list representing the order in which the cities are visited.
+     * @return The total distance of the route, or Integer.MAX_VALUE if the route is invalid.
+     */
+    public static int calculateDistance(int[][] distanceMatrix, List<Integer> route) {
+        int distance = 0;
+        for (int i = 0; i < route.size() - 1; i++) {
+            int d = distanceMatrix[route.get(i)][route.get(i + 1)];
+            if (d == Integer.MAX_VALUE) {
+                return Integer.MAX_VALUE;
+            }
+            distance += d;
+        }
+        int returnDist = distanceMatrix[route.get(route.size() - 1)][route.get(0)];
+        return (returnDist == Integer.MAX_VALUE) ? Integer.MAX_VALUE : distance + returnDist;
+    }
+
+    /**
+     * Generates all permutations of a given list of cities.
+     *
+     * @param cities A list of cities to permute.
+     * @return A list of all possible permutations.
+     */
+    private static List<List<Integer>> generatePermutations(List<Integer> cities) {
+        List<List<Integer>> permutations = new ArrayList<>();
+        permute(cities, 0, permutations);
+        return permutations;
+    }
+
+    /**
+     * Recursively generates permutations using backtracking.
+     *
+     * @param arr     The list of cities.
+     * @param k       The current index in the permutation process.
+     * @param output  The list to store generated permutations.
+     */
+    private static void permute(List<Integer> arr, int k, List<List<Integer>> output) {
+        if (k == arr.size()) {
+            output.add(new ArrayList<>(arr));
+            return;
+        }
+        for (int i = k; i < arr.size(); i++) {
+            Collections.swap(arr, i, k);
+            permute(arr, k + 1, output);
+            Collections.swap(arr, i, k);
+        }
+    }
+
+    /**
+     * Solves the Traveling Salesman Problem (TSP) using dynamic programming with the Held-Karp algorithm.
+     *
+     * @param distanceMatrix A square matrix where element [i][j] represents the distance from city i to city j.
+     * @return The shortest possible route distance visiting all cities exactly once and returning to the starting city.
+     * @throws IllegalArgumentException if the input matrix is not square.
+     */
+    public static int dynamicProgramming(int[][] distanceMatrix) {
+        if (distanceMatrix.length == 0) {
+            return 0;
+        }
+        int n = distanceMatrix.length;
+
+        for (int[] row : distanceMatrix) {
+            if (row.length != n) {
+                throw new IllegalArgumentException("Matrix must be square");
+            }
+        }
+
+        int[][] dp = new int[n][1 << n];
+        for (int[] row : dp) {
+            Arrays.fill(row, Integer.MAX_VALUE);
+        }
+        dp[0][1] = 0;
+
+        for (int mask = 1; mask < (1 << n); mask++) {
+            for (int u = 0; u < n; u++) {
+                if ((mask & (1 << u)) == 0 || dp[u][mask] == Integer.MAX_VALUE) {
+                    continue;
+                }
+                for (int v = 0; v < n; v++) {
+                    if ((mask & (1 << v)) != 0 || distanceMatrix[u][v] == Integer.MAX_VALUE) {
+                        continue;
+                    }
+                    int newMask = mask | (1 << v);
+                    dp[v][newMask] = Math.min(dp[v][newMask], dp[u][mask] + distanceMatrix[u][v]);
+                }
+            }
+        }
+
+        int minDistance = Integer.MAX_VALUE;
+        int fullMask = (1 << n) - 1;
+        for (int i = 1; i < n; i++) {
+            if (dp[i][fullMask] != Integer.MAX_VALUE && distanceMatrix[i][0] != Integer.MAX_VALUE) {
+                minDistance = Math.min(minDistance, dp[i][fullMask] + distanceMatrix[i][0]);
+            }
+        }
+
+        return minDistance == Integer.MAX_VALUE ? 0 : minDistance;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/graph/TravelingSalesmanTest.java b/src/test/java/com/thealgorithms/graph/TravelingSalesmanTest.java
new file mode 100644
index 00000000..b93c9f89
--- /dev/null
+++ b/src/test/java/com/thealgorithms/graph/TravelingSalesmanTest.java
@@ -0,0 +1,127 @@
+package com.thealgorithms.graph;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+public class TravelingSalesmanTest {
+
+    // Test Case 1: A simple distance matrix with 4 cities
+    @Test
+    public void testBruteForceSimple() {
+        int[][] distanceMatrix = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
+        int expectedMinDistance = 80;
+        int result = TravelingSalesman.bruteForce(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    @Test
+    public void testDynamicProgrammingSimple() {
+        int[][] distanceMatrix = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
+        int expectedMinDistance = 80;
+        int result = TravelingSalesman.dynamicProgramming(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    // Test Case 2: A distance matrix with 3 cities
+    @Test
+    public void testBruteForceThreeCities() {
+        int[][] distanceMatrix = {{0, 10, 15}, {10, 0, 35}, {15, 35, 0}};
+        int expectedMinDistance = 60;
+        int result = TravelingSalesman.bruteForce(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    @Test
+    public void testDynamicProgrammingThreeCities() {
+        int[][] distanceMatrix = {{0, 10, 15}, {10, 0, 35}, {15, 35, 0}};
+        int expectedMinDistance = 60;
+        int result = TravelingSalesman.dynamicProgramming(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    // Test Case 3: A distance matrix with 5 cities (larger input)
+    @Test
+    public void testBruteForceFiveCities() {
+        int[][] distanceMatrix = {{0, 2, 9, 10, 1}, {2, 0, 6, 5, 8}, {9, 6, 0, 4, 3}, {10, 5, 4, 0, 7}, {1, 8, 3, 7, 0}};
+        int expectedMinDistance = 15;
+        int result = TravelingSalesman.bruteForce(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    @Test
+    public void testDynamicProgrammingFiveCities() {
+        int[][] distanceMatrix = {{0, 2, 9, 10, 1}, {2, 0, 6, 5, 8}, {9, 6, 0, 4, 3}, {10, 5, 4, 0, 7}, {1, 8, 3, 7, 0}};
+        int expectedMinDistance = 15;
+        int result = TravelingSalesman.dynamicProgramming(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    // Test Case 4: A distance matrix with 2 cities (simple case)
+    @Test
+    public void testBruteForceTwoCities() {
+        int[][] distanceMatrix = {{0, 1}, {1, 0}};
+        int expectedMinDistance = 2;
+        int result = TravelingSalesman.bruteForce(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    @Test
+    public void testDynamicProgrammingTwoCities() {
+        int[][] distanceMatrix = {{0, 1}, {1, 0}};
+        int expectedMinDistance = 2;
+        int result = TravelingSalesman.dynamicProgramming(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    // Test Case 5: A distance matrix with identical distances
+    @Test
+    public void testBruteForceEqualDistances() {
+        int[][] distanceMatrix = {{0, 10, 10, 10}, {10, 0, 10, 10}, {10, 10, 0, 10}, {10, 10, 10, 0}};
+        int expectedMinDistance = 40;
+        int result = TravelingSalesman.bruteForce(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    @Test
+    public void testDynamicProgrammingEqualDistances() {
+        int[][] distanceMatrix = {{0, 10, 10, 10}, {10, 0, 10, 10}, {10, 10, 0, 10}, {10, 10, 10, 0}};
+        int expectedMinDistance = 40;
+        int result = TravelingSalesman.dynamicProgramming(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    // Test Case 6: A distance matrix with only one city
+    @Test
+    public void testBruteForceOneCity() {
+        int[][] distanceMatrix = {{0}};
+        int expectedMinDistance = 0;
+        int result = TravelingSalesman.bruteForce(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    @Test
+    public void testDynamicProgrammingOneCity() {
+        int[][] distanceMatrix = {{0}};
+        int expectedMinDistance = 0;
+        int result = TravelingSalesman.dynamicProgramming(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    // Test Case 7: Distance matrix with large numbers
+    @Test
+    public void testBruteForceLargeNumbers() {
+        int[][] distanceMatrix = {{0, 1000000, 2000000}, {1000000, 0, 1500000}, {2000000, 1500000, 0}};
+        int expectedMinDistance = 4500000;
+        int result = TravelingSalesman.bruteForce(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+
+    @Test
+    public void testDynamicProgrammingLargeNumbers() {
+        int[][] distanceMatrix = {{0, 1000000, 2000000}, {1000000, 0, 1500000}, {2000000, 1500000, 0}};
+        int expectedMinDistance = 4500000;
+        int result = TravelingSalesman.dynamicProgramming(distanceMatrix);
+        assertEquals(expectedMinDistance, result);
+    }
+}