Dijkstrov algoritmus na binarnej halde

harrison314

Potrebujem zimplementovat Dijkstrov algoritmus a narazil som na problem z binarnou hladou.
Chcem ju zimplementovat na vektore ( jazyk C, ono to musi byt velmi richle ) a potreboval by som vediet aka musi byt velka,co je vlastne moja prva cast otazky.

Druha cast sa tika toho, ze ak by bola halada prilis velka a musel by som jej velkost okresat ci vrcholi grafu , ktore su nspodu ( maju najvisiu hodnotu ) mozem nechat prepadnut do zabudnutia?

pipiak

Boze moj zlaty, moja gramatika je na bode mrazu, ale to co ty predvadzas ... sak ja by som to normalne zaradil za porusenie nejakych pravidiel fora toto:D
A co sa tyka otazky, netusim na co sa to pouziva, ale vpodstate by ma viac zaujimalo na co to pouzijes ty?

harrison314

To sa tu uz nik nevyjadruje k teme

c-ice

ja by sa vyjadril ale nedalo sa to čítať ...
Dijkstra je algoritmus na hľadanie najkratšej cesty z jedneho bodu do druhého http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Pre tych čo nevedia čo to je ...

ale nechapem ako ju chces implementovat na vektore... ja som to robil cez zretazene zoznamy v C++ pred necelým pol rokom takze si este pamatam ako to fungovalo ... ale moc sa mi to nechce vysvetlovat lebo ma z toho akurat tak porazí...

je potrebne mat niekde ulozene jednotlive Body, a hrany ... Bod ma svoju value a pointer na bod z ktoreho som sa tam dostal... Hrana ma zaciatok a koniec (typu bod) , hodnotu a meno(nepovinne ale lepsie sa mi stym pracovalo pri vypise) ....
dalej my sme hrany nacitavali zo suboru graf.txt ktory najavačši mal velkost 300bodov a z kazdeho bodu do kazdeho isla hrana to bolo okolo 125000 hran je to dost velke ?

aha teraz mi to docvaklo ty sa skôr pýtaš ako realizovať Binary Heap ?

a k tej druhej casti ten algoritmus Dijkstra je fakt dost dost rychli takze by som sa nebal a nesnazil sa to na silu nejak "optimalizovať" ...
mohol by si to trocha po slovensky alebo anglicky napisat ? lebo fakt sa to neda čitat...
ak tam je napisane o vyhadzovani bodov tak to nerob...

harrison314

Takze skusim to prelozit do slovenciny:
Aky maximalny pocet vrcholov bude v sebe obsahovat binarna halda ( binary heap ) , v zavisloti od pocetu vrcholov alebo hran v grafe.

javatar

zalezi od toho ake vsetky informacie budes mat vo vrchole binarnej haldy

harrison314

Aktualnu hodnotu a cislo vrcholu, popripade ukazovatel na nieco.

javatar

a hrany riesis ako? lebo co je mne zname tak binarna halda je implementaciou prioritneho frontu a cez front riesit graf? neviem ci presne rozumiem o co ti ide, ale ak potrebuje dijkstra tak na to potrebujes implementaciu tabulky (co sa da aj cez binarnu haldu, ale neaku vyhodu v tom nevidim) + nieco kde si ukladas najkratsiu cestu...

odpoved na uvodnu otazku -> ako do vrcholu binarnej haldy pchas len vrchol grafu potom bude halda mat halda pocet vrcholov rovny poctu vrcholov v grafe... ale co s hranami?

som mierne zmateny z toho co vlastne chces...

harrison314

graf riesim zoznamom susednosti ( matica sa mi nezmesti do pamate ),
ale mne sa zda ze graf v prilohe ( sory za kvalitu, kreslil som to narichlo), ked hldam najkratciu cestu z A do F,
v istej faze algoritmu bude mat halda v sebe bod D 3 krat.

Dijkstrov algoritmus na binarnej halde

Dijkstrov algoritmus na binarnej halde

Re: Dijkstrov algoritmus na binarnej halde

Re: Dijkstrov algoritmus na binarnej halde

Re: Dijkstrov algoritmus na binarnej halde

Re: Dijkstrov algoritmus na binarnej halde

Re: Dijkstrov algoritmus na binarnej halde

Re: Dijkstrov algoritmus na binarnej halde

Re: Dijkstrov algoritmus na binarnej halde

Re: Dijkstrov algoritmus na binarnej halde