Czy ktoś kiedyś implementował algorytm Dijkstry tak, aby uzyskać złożoność O(VlogV) jeśli chodzi o wierzchołki, i może się podzielić spostrzeżeniami co do trudności implementacji, ewentualnych wyników działania takiej wersji algorytmu (stała nie zabija złożoności? czyli czy w praktyce to nie jest wolniejsze od O(V^2) ) Czy też tak z tymi kopcami Fibonacciego i Dijkstrą jest jak z UFO, wielu słyszało ale prawie nikt nie widział? ;>
pzdr,
y.
na stronie www.algorytm.cad.pl jest opisany alg. D.
Hyh, nie pytałem o co chodzi w algorytmie Dijkstry tylko o to jak w praktyce wygląda poprawianie złożoności. Czy warto babrać się w implementację kopców Fibonacciego, czy efekt w stosunku do wysiłku nie jest zbyt imponujący?
pzdr,
y.
Hyh, nie pytałem o co chodzi w algorytmie Dijkstry tylko o to jak w praktyce wygląda poprawianie złożoności. Czy warto babrać się w implementację kopców Fibonacciego, czy efekt w stosunku do wysiłku nie jest zbyt imponujący?
pzdr,
y.
Efekt jest b. duzy. A jest jeszcze wiekszy jesli w ogole darujesz sobie Dijkstre i zaimplementujesz A*, o ile tylko mozesz w grafie okreslic sensowna metryke (jesli nie, no to zostaje Dijkstra).
Po diabla implementowac kopce, kiedy w C++ one juz sa zaimplementowane: #include<priority_queue>.
Javowcy moga tylko pozazdroscic. :-[
Dzięki, obadam A*. Co do zazdrości to 'javowcy' raczej nie mają czego zazdrościć (ale po co robić flame wara ;>), priority queue można zrobić na TreeSecie z własnym Comparatorem dla elementów zbioru (o ile mnie pamięć nie myli ;>
pzdr,
y.