Sinulle annetaan etäisyystaulukko, joka ilmaisee kunkin kahden kaupungin välisen etäisyyden. Kaupungit on numeroitu 1 \dots n.
Etäisyystaulukko voi näyttää vaikkapa seuraavalta: \begin{matrix} 0 & 2 & 2 & 1 & 8 \\ 2 & 0 & 9 & 1 & 2 \\ 2 & 9 & 0 & 8 & 3 \\ 1 & 1 & 8 & 0 & 3 \\ 8 & 2 & 3 & 3 & 0 \\ \end{matrix} Tässä tapauksessa kaupungit ovat 1 \dots 5. Esimerkiksi kaupunkien 2 ja 3 välinen etäisyys on 9. Tämä etäisyys on taulukossa rivin 2 sarakkeessa 3 sekä rivin 3 sarakkeessa 2.
Tehtäväsi on etsiä lyhin reitti, joka lähtee kaupungista 1, käy kaikissa muissa kaupungeissa ja palaa lopuksi takaisin kaupunkiin 1. Jos reittejä on useita, tulee valita reitti, joka siirtyy joka askeleella kaupunkiin, jonka numero on mahdollisimman pieni. Äskeisessä etäisyystaulukossa haluttu lyhin reitti on 1 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 4 \rightarrow 1, jonka pituus on 9.
Toteuta tiedostoon visitall.py funktio find_route, jolle annetaan etäisyystaulukko listana listoja. Funktion tulee palauttaa parina lyhimmän reitin pituus sekä esimerkki tavasta muodostaa reitti.
Voit olettaa, että kaupunkien määrä etäisyystaulukossa on välillä 2 \dots 8. Funktion tulee toimia tehokkaasti kaikissa tällaisissa tapauksissa.
def find_route(distances):
# TODO
if __name__ == "__main__":
distances = [[0, 2, 2, 1, 8],
[2, 0, 9, 1, 2],
[2, 9, 0, 8, 3],
[1, 1, 8, 0, 3],
[8, 2, 3, 3, 0]]
length, route = find_route(distances)
print(length) # 9
print(route) # [1, 3, 5, 2, 4, 1]
distances = [[0, 7, 5, 9, 6, 3, 1, 3],
[7, 0, 3, 2, 3, 3, 7, 8],
[5, 3, 0, 4, 2, 7, 7, 1],
[9, 2, 4, 0, 2, 3, 2, 4],
[6, 3, 2, 2, 0, 9, 5, 9],
[3, 3, 7, 3, 9, 0, 4, 5],
[1, 7, 7, 2, 5, 4, 0, 7],
[3, 8, 1, 4, 9, 5, 7, 0]]
length, route = find_route(distances)
print(length) # 18
print(route) # [1, 7, 4, 6, 2, 5, 3, 8, 1]