Witam.
Algorytm Dijkstry chyba wszyscy znaja ;)
Pytanko: Co to sa te kopce/stogi i jak je zaimplementowac, zeby poprawic czas dzialania wyzej wymienionego? (Gdzies w jakims opisie w necie znalazlem taka wskazowke, ale temat nie zostal rozwiniety :-/ )
Pozdravki.
Kopiec: struktura drzewiasta charakteryzująca się równomiernym rozkładem. Taka piramidka z ew. nie dokończonym ostatnim rzędem :)
Zwykle jednak kopca nie implementuje się na drzewkach, tylko na tablicy. Wystarczy bowiem zauwayżyć, że jeżeli szczyt drzewa umieścimy w i-tej komórce, to poddrzewa znajdować się będą w 2i i 2i+1 komórce.
Zazwyczaj zależy nam także na tym, by elementy na drzewie były ułożone w pewnej kolejności, ale to już inna bajka...
A optymalizacja... Hmm. Zapewne wolne wierzchołki należałoby umieścić w kopcu. [stuk]
Drobna uwaga: ta definicja stosuje sie do kopca binarnego a mamy jeszcze wiele smiesznych struktor danych zawierajacych w sobie slowo kopiec: kopiec dwumianowy, kopiec Fibonnaciego itd. Osobiscie polecam taki jeden ktorego nazyw nie pamietam :) a na ktorym wszytkie operacje wykonuje sie korzystajajac z funkcji union ktora zcala 2 kopce w jeden jadac po ich prawych krawedziach dodajac jako prawego syna mniejszego wieszcholka wiekszy wierzcholek (cos jak scalanie 2 posortowanych list) a nastepnie zamieniajac w drodze powrotnej lewe podrzewo z prawym :)
robilem kiedys unit dla Dijkstra tzn szukal najktotsza trase jakby ktos nie wiedzial do czego sluzy.
Sczerze powiem ze nie chce mi sie mocno grzebac i szukac bo to jakby mala czesc duzego projektu ale jak ktos chce to moge ten unit wpusic tu.
Moga tam byc w nim roznie inne smieci ale sedno powinno byc.
Chcecie?????????
Dla każdego wierzchołka wykonujemy funkcję Pobierz_Najmniejszy() oraz dodatkowo dla każdej krawędzi wykonujemy jedno porównanie (i ewentualnie podstawienie) w czasie sta-łym. Zatem złożoność czasowa zależy od tego jak zaprojektujemy funkcję Po-bierz_Najmniejszy().
Jeżeli zastosujemy proste, liniowe wyszukiwanie najmniejszego elementu, to otrzymamy zło-żoność O(V2+E). Gdybyśmy użyli do tego stogu, to otrzymamy O(VlogV+ElogV), co się opłaca w przypadku grafów rzadkich, a dla gęstych tylko pogarsza wynik. Najlepsze co mo-żemy zrobić to użyć kopców Fibbonacciego, dzięki którym otrzymamy złożoność O(V*logV+E) (ale to jest dość skomplikowane).
To akapit dot. zlozonosci czasowej Dijkstry z mojego opisu. Kopce Fibbonacciego, o ktorych wspomniano w ostatnim zdaniu, chyba faktycznie sa skomplikowane, gdyz nie moge w necie znalezc co to jest i jak z w/w algorytmem je polaczyc... wszelka pomoc jest dla mnie nieoceniona...
Pozdravki.