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

[set4812]

jezeli masz dane co do miast to w tablicy powinno wygloadac tak tab[i][j]- gdzie i to miasto 1 a j inne miasta porównywane w skrócie zmieniasz tylko wartosć j jezeli chcesz odnalezc najblizsze miasto

[kartin]

Użyj któregoś z algorytmów poszukiwania najkrótszej ścieżki np. Algorytm Dijkstry