Napisz procedurę
NajkrótszaTrasa :miasto_start_wiersz :miasto_koniec_kolumna :tabela_odległości
która zwraca najkrótszą trasę oraz najkrótszy czas przejazdu miedzy podanymi miastami.
Zmienna :tabela_odległości to tablica zapisana w postaci listy 4 elementowych list liczb oznaczających czas przejazdu (w godzinach) między miastami.
Poniższa tablica:
0 3 4 -1
-1 0 8 5
3 4 0 2
5 2 9 0
będzie mieć następującą wartość jako zmienna :tabela_odległości:
[ [0 3 4 -1] [-1 2 8 5] [3 4 0 2] [5 2 9 0] ]
i oznacza - co możemy wyczytać z pierwszego wiersza - że na przykład:
-
odległość z miasta o numerze 1 do miasta o numerze 1 wynosi 0
-
odległość z miasta o numerze 1 do miasta o numerze 2 wynosi 3 godziny
-
odległość z miasta o numerze 1 do miasta o numerze 3 wynosi 4 godziny
-
odległość z miasta o numerze 1 do miasta o numerze 4 wynosi -1 (nie istnieje dorga z miasta o numerze 1 do miasta o numerze 4)
Zauważmy, że czas przejazdu między miastem
x i
y może być inny niż czas przejazdu między miastem
y i
x. Co więcej jeśli istnieje możliwośc przejazdu z miasta
x do miasta
y to nie musi istnieć możliwość przejazdu z miasta
y do miasta
x.
Zmienna :miasto_start_wiersz oznacza numer miasta (numer wiersza) z którego wyjeżdżamy. Zmienna :numer_kolumny_miasto_koniec oznacza numer miasta (numer kolumny) do którego się udajemy.
Procedura powinna w wyniku zwrócić dwulementową listę, w której:
-
Pierwszy element oznacza numery wszystkich miast począwszy od początkowego a skończywszy na docelowym znajdujące się na najkrótszej trasie między miastem początkowym a docelowym.
-
Drugi element oznacza czas przejazdu najkrótszą trasą
Na przykład:
? NajkrótszaTrasa 2 3 [ [0 -1 4 8] [-1 0 -1 9] [-1 -1 0 7] [-1 -1 1 0]]
powinno w wyniku zwrócić następującą listę:
[243 10]
co oznacza, że najkrótsza trasa z miasta 2 do miasta 3 biegnie z miasta 2 do miasta 4 i kończy sie w mieście 3 oraz trwa 10 godzin.