Kiertomatka

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]