A: {'A': 0, 'D': 5, 'B': 7, 'F': 11, 'E': 14, 'C': 15, 'G': 22}
B: {'B': 0, 'A': 7, 'E': 7, 'C': 8, 'D': 9, 'F': 15, 'G': 16}
C: {'C': 0, 'E': 5, 'B': 8, 'F': 13, 'G': 14, 'A': 15, 'D': 17}
D: {'D': 0, 'A': 5, 'F': 6, 'B': 9, 'E': 14, 'C': 17, 'G': 17}
E: {'E': 0, 'C': 5, 'B': 7, 'F': 8, 'G': 9, 'A': 14, 'D': 14}
F: {'F': 0, 'D': 6, 'E': 8, 'A': 11, 'G': 11, 'C': 13, 'B': 15}
G: {'G': 0, 'E': 9, 'F': 11, 'C': 14, 'B': 16, 'D': 17, 'A': 22}

Floyd-Warshall algoritmus

A: {'A': 0, 'D': 5, 'B': 7, 'F': 11, 'E': 14, 'C': 15, 'G': 22}
B: {'B': 0, 'A': 7, 'E': 7, 'C': 8, 'D': 9, 'F': 15, 'G': 16}
C: {'C': 0, 'E': 5, 'B': 8, 'F': 13, 'G': 14, 'A': 15, 'D': 17}
D: {'D': 0, 'A': 5, 'F': 6, 'B': 9, 'E': 14, 'C': 17, 'G': 17}
E: {'E': 0, 'C': 5, 'B': 7, 'F': 8, 'G': 9, 'A': 14, 'D': 14}
F: {'F': 0, 'D': 6, 'E': 8, 'A': 11, 'G': 11, 'C': 13, 'B': 15}
G: {'G': 0, 'E': 9, 'F': 11, 'C': 14, 'B': 16, 'D': 17, 'A': 22}

vidíme, že máme zle vypočítanú uhlopriečku (majú byť nuly)

Priebeh:

Untitled.png

Kostra grafu

image.png

Cena kostry je súčet ohodnotení hrán v kostre ... $7+5+5+6+8+11 = 42$

image.png

Cena je $7+9+5+15+9+11=56$ ...

Aká je minimálna cena kostry ... najlacnejšia kostra

image.png

Cena je 39 ;-) ...

Na papieri jednoducho vidíme, či je/nie je cyklus ... naprogramovať buď spustíme prehľadávanie grafu (zelených hrán) alebo musíme si pamätať do ktorého komponentu patria jednotlivé vrcholy a spájať komponenty (Union&Find)

image.png

vyberáme najlacnejšiu hranu ... môžeme použiť prioritný rad

A->D 5
B->D 9
E->D 15
E->F 8
E->G 9

teda v Pythone

(5, 'A', 'D')
(9, 'B', 'D')
(vzdialenost, skade, kam) ... skade uz je spracovany vcrhol

Nenastavili sme spracovanie vrcholu ...

Untitled.png

aj cena ...