Witam, poszukuję odpowiedzi na dwa pytania, na które nie mogę znaleźć odpowiedzi, mianowicie
o ile może zmienić się liczba silnie spójnych składowych w grafie w wyniku dodania jednej krawędzi oraz dlaczego algorytm Dijkstry nie może być używany dla grafów z ujemnymi wagami krawędzi?
dziękuję za wszelką pomoc :)
0
1
Ad2: ujemne cykle a nie krawędzie. Bo na ujemnym cyklu możesz nieskończenie długo obniżać wagę ścieżki.
1
Ad 1. Od 0 do max(S,S2/4), gdzie S - ilość silnie spójnych składowych w grafie wejściowym.
Ad 2. Bo się zapętli.