This is Traveling Salesman Problem. I need help because I don't understand how to make us start and end at different points. Below I have given the code for solving the problem in the usual way. Here we start and end at the same point.
def Min(lst,myindex):
return min(x for idx, x in enumerate(lst) if idx != myindex)
def Delete(matrix,index1,index2):
del matrix[index1]
for i in matrix:
del i[index2]
return matrix
def PrintMatrix(matrix):
print("---------------")
for i in range(len(matrix)):
print(matrix[i])
print("---------------")
n=int(input())
matrix=[]
H=0
PathLenght=0
Str=[]
Stb=[]
res=[]
result=[]
StartMatrix=[]
for i in range(n):
Str.append(i)
Stb.append(i)
for i in range(n): matrix.append(list(map(int, input().split())))
for i in range(n):StartMatrix.append(matrix[i].copy())
float(inf)
for i in range(n): matrix[i][i]=float('inf')
while True:
for i in range(len(matrix)):
temp=min(matrix[i])
H+=temp
for j in range(len(matrix)):
matrix[i][j]-=temp
for i in range(len(matrix)):
temp = min(row[i] for row in matrix)
H+=temp
for j in range(len(matrix)):
matrix[j][i]-=temp
NullMax=0
index1=0
index2=0
tmp=0
for i in range(len(matrix)):
for j in range(len(matrix)):
if matrix[i][j]==0:
tmp=Min(matrix[i],j)+Min((row[j] for row in matrix),i)
if tmp>=NullMax:
NullMax=tmp
index1=i
index2=j
res.append(Str[index1]+1)
res.append(Stb[index2]+1)
oldIndex1=Str[index1]
oldIndex2=Stb[index2]
if oldIndex2 in Str and oldIndex1 in Stb:
NewIndex1=Str.index(oldIndex2)
NewIndex2=Stb.index(oldIndex1)
matrix[NewIndex1][NewIndex2]=float('inf')
del Str[index1]
del Stb[index2]
matrix=Delete(matrix,index1,index2)
if len(matrix)==1:break
for i in range(0,len(res)-1,2):
if res.count(res[i])<2:
result.append(res[i])
result.append(res[i+1])
for i in range(0,len(res)-1,2):
for j in range(0,len(res)-1,2):
if result[len(result)-1]==res[j]:
result.append(res[j])
result.append(res[j+1])
print("----------------------------------")
print(result)
for i in range(0,len(result)-1,2):
if i==len(result)-2:
PathLenght+=StartMatrix[result[i]-1][result[i+1]-1]
PathLenght+=StartMatrix[result[i+1]-1][result[0]-1]
else: PathLenght+=StartMatrix[result[i]-1][result[i+1]-1]
print(PathLenght)
print("----------------------------------")
input()
This code works like this:
- input 4
- input 4x4 matrix like this:
0 10 1 1
10 0 1 5
1 1 0 10
1 5 10 0
- result: 1->4 4->2 2->3 3->1 (8)
I done this question like this on JS:
let towns = [
[0, 28, 58, 13, 24, 25, 31, 64],
[28, 0, 82, 15, 52, 27, 33, 54],
[58, 82, 0, 67, 82, 64, 49, 97],
[13, 15, 67, 0, 37, 12, 18, 69],
[24, 52, 82, 37, 0, 49, 53, 40],
[25, 27, 64, 12, 49, 0, 15, 81],
[31, 33, 49, 18, 53, 15, 0, 70],
[64, 54, 97, 69, 40, 81, 70, 0],
];
let path = [];
let counter = 0;
let minPath = 10000;
let minCounter;
for (let i1 = 0; i1 <= 7; i1++) {
for (let i2 = 0; i2 <= 7; i2++) {
for (let i3 = 0; i3 <= 7; i3++) {
for (let i4 = 0; i4 <= 7; i4++) {
for (let i5 = 0; i5 <= 7; i5++) {
for (let i6 = 0; i6 <= 7; i6++) {
for (let i7 = 0; i7 <= 7; i7++) {
for (let i8 = 0; i8 <= 7; i8++) {
if (
i1 != i2 &&
i1 != i3 &&
i1 != i4 &&
i1 != i5 &&
i1 != i6 &&
i1 != i7 &&
i1 != i8 &&
i2 != i3 &&
i2 != i4 &&
i2 != i5 &&
i2 != i6 &&
i2 != i7 &&
i2 != i8 &&
i3 != i4 &&
i3 != i5 &&
i3 != i6 &&
i3 != i7 &&
i3 != i8 &&
i4 != i5 &&
i4 != i6 &&
i4 != i7 &&
i4 != i8 &&
i5 != i6 &&
i5 != i7 &&
i5 != i8 &&
i6 != i7 &&
i6 != i8 &&
i7 != i8
) {
path[counter] =
i1 +
1 +
" → " +
(i2 + 1) +
" → " +
(i3 + 1) +
" → " +
(i4 + 1) +
" → " +
(i5 + 1) +
" → " +
(i6 + 1) +
" → " +
(i7 + 1) +
" → " +
(i8 + 1);
console.log(path[counter]);
if (
towns[i1][i2] +
towns[i2][i3] +
towns[i3][i4] +
towns[i4][i5] +
towns[i5][i6] +
towns[i6][i7] +
towns[i7][i8] <
minPath
) {
minPath =
towns[i1][i2] +
towns[i2][i3] +
towns[i3][i4] +
towns[i4][i5] +
towns[i5][i6] +
towns[i6][i7] +
towns[i7][i8];
console.log(minPath);
minCounter = counter;
}
counter += 1;
}
}
}
}
}
}
}
}
}
console.log(
"Shortest Way: " +
path[minCounter] +
"(" +
minPath +
" KM.)"
);