Oto akcyza:

Niech G będzie ważonym grafem ukierunkowanym z n wierzchołkami i krawędziami m, gdzie wszystkie krawędzie mają masę dodatnią. Cykl kierowany to ukierunkowana ścieżka, która zaczyna się i kończy przy tym samym wierzchołku i zawiera co najmniej jedną krawędź. Daj algorytm O (n ^ 3), aby znaleźć ukierunkowany cykl w G o minimalnej masie całkowitej. Częściowy kredyt zostanie przyznany za algorytm O ((n ^ 2) * m).

Oto mój algorytm.

RobięDFS. Za każdym razem, gdy znajdęback edge, Wiem, że mam ukierunkowany cykl.

Potem tymczasowo cofnę się wzdłużparent array (dopóki nie przejdę przez wszystkie wierzchołki w cyklu) i nie obliczętotal weights.

Następnie porównujętotal weight tego cyklu zmin. min zawsze pobiera minimalną całkowitą wagę. Po zakończeniu DFS znajduje się także nasz minimalny cykl kierowany.

Ok, to o złożoności czasu.

Szczerze mówiąc, nie znam złożoności czasowej mojego algorytmu.

W przypadku DFS przejście wykonuje O (m + n) (jeśli m jest liczbą krawędzi, a n jest liczbą wierzchołków). Dla każdego wierzchołka może wskazywać na jednego z jego przodków, tworząc w ten sposób cykl. Gdy cykl zostanie znaleziony, O (n) zajmuje podsumowanie całkowitej masy.

Myślę więc, że całkowity czas to O (m + n * n). Ale oczywiście jest źle, jak stwierdzono w akcyzie, optymalnym czasem jest O (n ^ 3), a normalnym czasem jest O (m * n ^ 2).

Czy ktoś może mi pomóc:

Czy mój algorytm jest poprawny?Jaka jest złożoność czasu, jeśli mój algorytm jest poprawny?Czy jest jakiś lepszy algorytm dla tego problemu?