Rozumiem, że w tej macierzy zapisane są odległości. Korzystaj z tego może jak z bazy danych, tzn. niech ta macierz służy tylko do odczytu odległości i nic więcej. Mając macierz np. 3x3, stwórz sobie prostą listę, czy tablicę jednowymiarową z indeksami symbolizujące miasta, a jednocześnie będą to indeksy macierzy sąsiedztwa:
int [] nodes = new int[3];
for(int i = 0; i < nodes.length; i++)
nodes[i] = i;
Teraz tylko musisz wykorzystać powyższą tablicę do generowania wszystkich kombinacji, scieżek.
Samą odległość mając ścieżkę w postaci np {0, 1, 2, 0} obliczyć jest już bardzo prosto.
int[][] distances = {{0, 5, 10},
{5, 0, 4},
{10, 4, 0}};
int [] tspProposition = {0, 1, 2, 0};
int distance = 0;
for(int i = 0; i < tspProposition.length -1; i++)
{
int x = tspProposition[i];
int y = tspProposition[i + 1];
distance += distances[x][y];
}
System.out.println(distance);