Algorytm Dijkstry NicNieUmiem: Cześć, umiem wyznaczyć najkrótszą ścieżkę w grafie widząc go, natomiast mam zadanie, z którym nie spotkałem się na ćwiczeniach i nie jestem pewien czy dobrze myślę. ZADANIE: Po zastosowaniu algorytmu Dijkstry dla pewnego grafu o zbiorze wierzchołków {a, b, . . . , i} poszukującego najkrótszych ścieżek z wierzchotka a do pozostałych wierzchołków otrzymano na końcu następujące wektory etykiet: wektor długości ścieżek (etykiety lewe): l = (0, 17, 15, 3, 5, 5, 7, 16, 2), wektor poprzedników (etykiety prawe): p = (−, c, g, i, i, a, a, c, a). Na tej podstawie wyznacz najkrótsze ścieżki z a do b oraz z a do d. Znajdź wagi każdej z krawędzi na tych ścieżkach. Czy te odpowiedzi są poprawne ? Najkrótsza a−>b (17,c) I ścieżka z a do b wygląda tak: a−>g−>c−>b Wagi: ag 7 gc 8 cb 2 Najkrótsza a−>d (3,i) a−>i−>d ai 2 id 1

Pytający: Tak.