Złożoność algorytmu dijkstry + magiczne piątki

Witam!

Proszę o pomoc w rozwiązaniu pewnego problemu. Otóż musiałem napisać program który znajduje najkrótszą ścieżkę w grafie skierowanym dla dwóch wierzchołków połączonych przez k-tą co do wielkości krawędź. Kiedy owa k-ta krawędź została(koniecznie za pomocą algorytmu "magiczne piątki") znaleziona należało wyliczyć najkrótszą ścieżkę między wierzchołkami które łączy krawędź w taki sposób że szukamy z punktu a ->b oraz b->a za pomocą algorytmu Dijkstry.

I teraz tu jest problem bo program ma działać w czasie O(|V| * |V|), gdzie V oznacza zbiór wierzchołków grafu. Wg moich teorii za nic nie mogę osiągnąć takiego wyniku. Bo tak: algorytm "magicznych piątek" działa w czasie liniowym, a że szukaliśmy krawędzi to będzie wynosił O(|E|), gdzie E oznacza zbiór krawędzi. Algorytm Dijkstry wykonujemy 2 razy i czasie O(|E| * log |V|) co daje złożoność końcową O(|E| + |E| * log |V|).

Na pewno musiałem popełnić gdzieś błąd albo przyjąć nieprawdziwe założenia podczas liczenia złożoności, więc proszę w wskazanie tego miejsca i wyjaśnienie dlaczego tak a nie inaczej. Sprawa jest dość paląca i nie ukrywam ze zależy mi na czasie.

Z góry dziękuję i pozdrawiam

http://pl.wikipedia.org/wiki/Algorytm_Dijkstry#Z.C5.82o.C5.BCono.C5.9B.C4.87
Najprostsza wersja Dijkstry ma złożoność O(|V|^2).

tak, ale zapomniałem dodać że moja Dijkstra ma zaimplementowaną kolejkę przez kopiec czyli złożoność dijkstry wychodzi O(|E|*log|V|).

Ale faktycznie jeśliby napisać "naiwną" implementację kolejki poprzez zwykłą tablicę to złożoność wychodziłaby taka jak potrzeba. Tylko czy w takim wypadku magiczne piątki w jakis sposób wpływają na złożoność całego algorytmu? A może jest inne wytłumaczenie ?

Algorytm Select oparty na Magicznych piątkach ma złożoność O(n).

Czyli Magiczne Piątki + Dijkstra = O(E) + O(V^{2) = O(V}2) ponieważ O(E) zawiera się w O(V^2).

Pamiętaj że O(f) to zbiór funkcji asymptotycznie nie większych od f. Zapis f(n) = O(f(n)) jest matematycznie niepoprawny, ale powszechnie stosowany. Oczywiście od razu widać że mamy do czynienia z zawieraniem się, a nie równością, a więc można przymknąć oko na takie uproszczenie zapisu.

Jeśli w naszym algorytmie jest stała liczba pętli/ podprocedur, powiedzmy sto miliardów, a asymptotycznie najbardziej złożona pętla/ podprocedura ma złożoność X to cały algorytm ma zlożoność X. Inaczej mówiąc: c * O(n) = O(n), o ile c jest stałą. Dlaczego zachodzi równość? Ponieważ w zbiorze O(n) dla każdej funkcji istnieje funkcja rosnąca dokładnie c razy wolniej, więc pomnożenie każdej funkcji przez stałą da identyczny zbiór (albo: każda funkcja z nowego zbioru istniała także w starym).

Algorytm wygląda tak:

• wybierasz k-tą co do wielkości krawędź,
• startujesz Dijsktrą ze źródła, aż dojdziesz do ktoregoś z końców wybranej krawędzie,
• zapamiętujesz wybraną ścieżkę,
• startujesz Dijsktrą z drugiego końca wybranej krawędzi, aż dojdziesz do ujścia,
• łączysz poprzednią ścieżkę, wybraną krawędź i obecną ścieżkę,

Kopce binarne implementuje się gdy |E| * log |V| nalezy do o(|V|^2) (zwróć uwagę na małe "o").

Teraz rozumiem. W takim wypadku należało tak skonstruować algorytm dijkstry żeby działał w czasie kwadratowym i ot cała zagadka rozwiązana ;) Dziękuję za pomoc!