-
Notifications
You must be signed in to change notification settings - Fork 266
/
TravellingSalesman.c
116 lines (105 loc) · 3.78 KB
/
TravellingSalesman.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/*
* Traveling Salesman Problem in C
* Using a distance matrix to represent an undirected graph.
* Objective: Find the shortest path that visits all vertices without
*repeating any, and returns to the starting vertex.
*
* 6
* (4)-----(0)
* | \ / \
* | \ 3/ \2
* | \/ \
* 3| /\ (1)
* | / 3\ 4/ |
* | / \ / |
* (3)-----(2) |
* | 7 |
* | | 3
* --------------
*
* Distance Matrix
* 0 1 2 3 4
* 0 0 2 - 3 6
* 1 2 0 4 3 -
* 2 - 4 0 7 3
* 3 3 3 7 0 3
* 4 6 - 3 3 0
*/
#include <stdbool.h>
#include <stdio.h>
#define VERTICES 5
#define INFINITY 429496729
int tempSolution[VERTICES];
int bestSolution[VERTICES];
bool visited[VERTICES];
int bestSolutionValue = INFINITY;
int currentSolutionValue = 0;
int matrix[VERTICES][VERTICES] = {{0, 2, INFINITY, 3, 6},
{2, 0, 4, 3, INFINITY},
{INFINITY, 4, 0, 7, 3},
{3, 3, 7, 0, 3},
{6, INFINITY, 3, 3, 0}};
void travelingSalesmanAux(int x) {
// If the current solution value is already greater than the best solution,
// stop as it can't be the best solution
if (currentSolutionValue > bestSolutionValue)
return;
if (x == VERTICES) { // If x == VERTICES, it means the temporary solution
// array is complete
int distance = matrix[tempSolution[x - 1]][tempSolution[0]];
// If a better (shorter) solution is found
if (distance < INFINITY &&
currentSolutionValue + distance < bestSolutionValue) {
bestSolutionValue =
currentSolutionValue +
distance; // Update the best solution with the new better one
// Copy the entire temporary solution array to the best solution array
for (int i = 0; i < VERTICES; ++i) {
bestSolution[i] = tempSolution[i];
}
}
return;
}
int last = tempSolution[x - 1]; // 'last' holds the number of the last vertex
// in the temporary solution array
// Loop through all columns in the matrix on the row of the last vertex in the
// temporary solution array
for (int i = 0; i < VERTICES; i++) {
// If the i-th vertex hasn't been visited, and the matrix value is less than
// INFINITY
if (!visited[i] && matrix[last][i] < INFINITY) {
visited[i] = true; // Mark as visited
tempSolution[x] =
i; // Add the current vertex to the temporary solution array
currentSolutionValue += matrix[last][i]; // Increment the path total
travelingSalesmanAux(x + 1); // Recursively call for the next vertex
currentSolutionValue -=
matrix[last][i]; // Decrease the path total if not finished yet
visited[i] = false; // Mark the vertex as unvisited so it can be used
// again by another vertex
}
}
}
void travelingSalesman(int start) {
visited[start] = true; // Mark the starting vertex as visited (0)
tempSolution[0] = start; // Place vertex 0 in the first position of the
// temporary solution array
travelingSalesmanAux(
1); // Call the auxiliary function for the traveling salesman problem
}
void initializeArrays() {
for (int i = 0; i < VERTICES; i++) {
visited[i] = false;
tempSolution[i] = -1;
bestSolution[i] = -1;
}
}
int main() {
initializeArrays();
travelingSalesman(0);
printf("Minimum path cost: %d\n", bestSolutionValue);
for (int i = 0; i < VERTICES; i++) {
printf("%d, ", bestSolution[i]);
}
printf("\n\n");
}