ASD e 02 2005 4

Egzamin ASD

Studia dzienne, 7go lutego 2005

Nazwisko............................................. Nr studenta............Nr grupy

Zadanie 4(10punktów)

	Bukowiec	Lesko	Solina	1 Wetlina	! Ustrzyki D.	^1 Ustrzyki G. I
Bukowiec	.	36	15	31	1	1
Lesko	1 36	_	19		48
Solina	15	1 19	-	1	37	1 1
Wetlina	31	1			i	15
Ustrzyki D.		1 48	37	•	1	^47 i
Ustrzyki G.		J	J	15	47	_

Mieszkający w Lesku pewien rozwoziciel mleka każdego dnia tygodnia wyrusza z towarem do jednego (za każdym razem do innego) z okolicznych miast i wraca do Leska. Z atlasu drogowego odczytał odległości po między sąsiadującymi ze sobą miejscowościami (patrz tabelka), a ponieważ był z wykształcenia informatykiem, błyskawicznie zastosował pewien algorytm, który pozwolił mu na zminimalizowanie długości trasy przebytej w ciągu tygodnia.

Polecenia:

(a)    Podaj nazwę algorytmu, który Twoim zdaniem zastosował mleczarz do rozwiązania problemu.

(b)    Wypisz kolejność, w jakiej miasta były dołączane do budowanego przez algorytm rozwiązania..(Uwzględniamy leksykograficzny porządek krawędzi o tej samej wadze!)

(c)    Narysuj graf reprezentujący drogi przebyte w ciągu tygodnia przez mleczarza.