ASD ep 02 2005 5

Algorytmy i Struktury Danych Egzamin poprawkowy 16 lutego 2005

Imię i nazwisko......................................................Nr indeksu.........................

Zadanie 5 Mieszkający w Lesku pewien rozwoziciel mleka każdego dnia wyrusza z towarem w trasę do pewnych okolicznych miast. Od pewnego czasu właściciel okolicznych gruntów, przez które przebiegają drogi łączące miasta, wprowadził miesięczny abonament (myto) za korzystanie z każdego odcinka drogi (patrz tabelka). Ponieważ rozwoziciel mleka był z wykształcenia informatykiem, błyskawicznie zastosował pewien algorytm do znalezienia takich połączeń między miastami, żeby każdego miesiąca płacić jak najmniej i jednocześnie móc swobodnie przemieszczać się między miastami.

Polecenia:    :

a)    Podaj nazwę i złożoność algorytmu zastosowanego Twoim zdaniem przez informatyka.

b)    Przedstaw kolejne etapy działania tego algorytmu i wypisz kolejność w jakiej połączenia były kolejno

wybierane przez zastosowany algorytm.    i

c)    Wylicz ile Mleczarz musi zapłacić miesięcznie za korzystanie z dróg.

d)    Narysuj graf reprezentujący ostateczne rozwiązanie.

- —■ "• *•••*••■	| Bukowiec | Lesko | Solina | Wetlina			| Ustrzyki D. | Ustrzyki G. |
Bukowiec	1 36 | 15 | 31 | | |
Lesko	36 | - | 19 | | 48				.............'....... 1
Solina 15 | 19		-		37
Wetlina 31 | | | 1 15
Ustrzyki D. j	......^_ | .....48 | 37			- .....1 '........47 |
Ustrzyki G. |	......................1...............“	1 «		47 | - |