Najkrótszą trasa przejazdu, Skrypt komiwojażera Opcje

[Michauuu]

Cześć wszystkim,
Muszę napisać w php skrypt, który będzie wyznaczał najkrótszą trasę między miastem startowym a końcowym. W moim przypadku program nie musi zwracać uwagi na warunki jezdne, po prostu najkrótsza trasa przejazdu.
Z danych wejściowych mam 49 miast. Program powinien też się wykonywać w jakimś przyzwoitym czasie ([49 – 2]! kombinacji).

Myślałem o zdeklarowaniu tablicy dwuwymiarowej przechowywującej informację, z jakimi innymi miastami miasto ma bezpośrednie połączenie drogowe i jak długa jest trasa pomiędzy tymi miastami.

[PHP] pobierz, plaintext 
$tablica[1][2] = 100; /* pomiędzy miastem 1 i 2 występuje połączenie drogowe mające 100 km */
$tablica[1][3] = null; /* pomiędzy miastem 1 i 2 nie ma połączenia */
[PHP] pobierz, plaintext 

Tak miałby wyglądać zapis danych, ale co do samego programu nie mam pojęcia jak go wykonać. Nie widzi mi się sprawdzanie każdej kombinacji i zapamiętywanie sumy, z drugiej strony algorytm najbliższego sąsiada mógłby tylko wydłużyć trasę.

Moglibyście podsunąć mi jakieś rozwiązanie.
B. Dzięki