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).

iN

14-06-07 15:

(b)

(c)