Kopia DSC00537

I . tita skierowanego grafu ważonego o N węzłach, którego struktura jest znana w postaci macierzy incyćtmcji O napisać pseudokod algorytmu, który wyznacza dowolną ścieżkę między wskazanymi węzłami: źródłowym S i docelowym T (jednym). Ponadto algorytm powinien zwracać informację o długości tej ścieżki (rozumianej jako suma wag krawędzi ją tworzących, oraz o wadze krawędzi, która w tej ścieżce ma wagę najmniejszą. Można wykorzystać jako punkt wyjścia jeden z algorytmów utworzonych w ramach zajęć ćwiczeniowych. Przyjąć „naturalny” sposób etykietowania węzłów grafu, tzn.: „i”, „2”,.... „N”.

(£) Przekształcić poniższy pseudokod algorytmu Euklidesa służącego do wyznaczania największego wspólnego dzielnika pary nieujemnych liczb całkowitych a i b tak, by zwracana była wartość najmniejszej wspólnej wielokrotności tej samej paty liczb, int Euklidfa, b)

{

if (a < b) a b; if (b = 0) return (0); trhile (b 0} do

C

r <— a mod b; a <- b; b ś- r;

. §

return (a); ł

A

Na rys. (a) pokazany jest graf z wagami, a na rysunkach (b) i (c) pokazane są dwa różne sposoby oznaczenia etykietami jego krawędzi za pomocą liter a, b,.... n w kolejności rosnących wag.

(a)    Zastosuj algorytm Kruskala do grafu o krawędziach uporządkowanych tak jak na rys. (b). Narysuj otrzymane minimalne drzewo spinające i podaj jego wagę.

(b)    Powtórz zadanie (a), kiedy krawędzie sa uporządkowane tak, jak na rysunku (c).

Wyszukiwarka

Podobne podstrony:
Kopia DSC00538 Wstęp do aigorytmizacji l. Dla skierowanego grafu ważonego o N węzłach, którego struk
Kopia DSC00538 Wstęp do aigorytmizacji l. Dla skierowanego grafu ważonego o N węzłach, którego struk
obraz5 (14) wersałnej żyzności; z drugiej strony, chodzi o scenariusz inicjacyjny, którego struktur
Kopia DSC00518 środowiskoKM— hodowla    wJim ^ szczep wyselekcjonowanyRys. Vl-8.7. Sk
Kopia DSC00556 Dlaczego Lepsza odporność na "stres”: jeśli uprawy mogą byt odporniejsze naj gra
Kopia DSC00557 i >?wo może redukować oddziaływanie na środowisko produkcji żywności i procesów pr
33 kopia(1) Trudno dostrzec w nieprzezroczystym czajniczku miejsce, do którego sięga woda w dziobku.
Kopia DSC00539 KJenmelc informatyka, studia stacjonarne l stopnia wstęp do algorytm izucji, sem. //
DSC00505 Replikacja DNA To proces w wyniku, którego na każdej z nici macierzystego DNA dochodzi do s

więcej podobnych podstron