Implementacja kopca binarnego w algorytmie Dijkstry

[betanddontcare]

Witam serdecznie,
Analizuję jeden z artykułów, w którym dokonano analizy szybkości działania algorytmów Dijkstry z różnymi implementacjami kolejki priorytetowej. Zastanawia mnie w jaki sposób można dokonać analizy tego zagadnienia dla rzeczywistego problemu wyznaczania tras przejazdu. Jak wyglądałoby takie drzewo binarne w realnej sytuacji? Przecież graf odwzorowujący sieć drogową może posiadać węzły, które posiadają połączenie z przykładowo 3 innymi węzłami. Te 3 węzły byłyby przecież węzłami dziećmi dla rodzica i powinny znaleźć się na tym samym poziomie. Czy użycie kopca binarnego w takich sytuacjach jest niemożliwe? Czy zamiast tego należy rozważyć kopiec d-arny czy po prostu źle zrozumiałem koncepcję kopca binarnego?

[Dasio11]

Źle rozumiesz, w jaki sposób używa się kopca binarnego w algorytmie Dijkstry. Struktura grafu, do którego stosuje się algorytm Dijkstry, nie ma żadnego związku ze strukturą kopca pełniącego rolę kolejki priorytetowej. Jeśli więc dla przykładu Radom jest połączony drogami z Krakowem, Warszawą i Rzeszowem, to nie ma żadnego powodu, żeby w kopcu Kraków, Warszawa i Rzeszów miały stać się dziećmi Radomia.

[betanddontcare]

Źle rozumiesz, w jaki sposób używa się kopca binarnego w algorytmie Dijkstry. Struktura grafu, do którego stosuje się algorytm Dijkstry, nie ma żadnego związku ze strukturą kopca pełniącego rolę kolejki priorytetowej. Jeśli więc dla przykładu Radom jest połączony drogami z Krakowem, Warszawą i Rzeszowem, to nie ma żadnego powodu, żeby w kopcu Kraków, Warszawa i Rzeszów miały stać się dziećmi Radomia.

Tak też czułem. No dobrze, ale czy mógłbyś omówić dosłownie w kilku zdaniach jak działa kopiec z Dijkstrą np: w tej praktycznej sytuacji (sieć drogowa Rumunii):

Kod: Zaznacz cały

https://i.ibb.co/71Dxnyc/romania.jpg

Czy kopiec budowany jest przed implementacją Dijkstry, czy w trakcie? Co jest kluczem węzła?
Z góry dziękuję za odpowiedź. Bardzo mało jest praktycznych przykładów użycia kopców z algorytmem Dijkstry.

[Dasio11]

Przyjmijmy, że wierzchołki grafu są numerowane liczbami od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\), a wierzchołek początkowy ma numer \(\displaystyle{ s}\). Algorytm Dijkstry dla każdego wierzchołka \(\displaystyle{ i}\) pamięta liczbę \(\displaystyle{ d[{i}]}\), która jest odległością tego wierzchołka od \(\displaystyle{ s}\) po najkrótszej obecnie znanej ścieżce. Kiedy algorytm się zakończy, ta liczba będzie się pokrywać z prawdziwą odległością \(\displaystyle{ s}\) do \(\displaystyle{ i}\). Kopiec składa się z par \(\displaystyle{ (d, i)}\), gdzie \(\displaystyle{ i}\) jest numerem wierzchołka a \(\displaystyle{ d}\) jest wartością \(\displaystyle{ d[{i}]}\) w momencie wkładania pary na kopiec. Kopiec \(\displaystyle{ Q}\) jest posortowany względem pierwszej współrzędnej, tak że bliżej szczytu kopca są pary \(\displaystyle{ (d, i)}\) o małej wartości \(\displaystyle{ d}\).

Algorytm działa według pseudokodu:

Kod: Zaznacz cały

D[1...n] = nieskończoność, D[s] = 0
Q <-- { ( D[s], s ) }
dopóki Q nie jest puste: 
    wyjmij z Q takie ( d, i ), dla którego d jest najmniejsze
    jeśli d != D[i], kontynuuj
    
    dla każdego sąsiada j wierzchołka i:
        d <-- D[i] + w(i, j)
        jeśli d < D[j]:
            D[j] = d
            Q <-- Q + { ( D[j], j ) } //(nawet jeśli w Q jest jakaś inna para (d', j))

W szczególności: kopiec jest budowany w trakcie działania algorytmu, a kluczem węzła jest obecnie wyliczona odległość wierzchołka od \(\displaystyle{ s}\).

Na podanym grafie z początkiem w Iasi algorytm umieszczałby miasta na kopcu w taki sposób:

Kod: Zaznacz cały

Włóż Iasi <0>;

Zdejmij Iasi <0>;
Włóż Neamt <85.8> i Vaslui <58.4>;

Zdejmij Vaslui <58.4>;
Włóż Hirsova <275.7> i Fagaras <287.8>;

Zdejmij Neamt <85.8>;
Włóż Urziceni <400.8>, Fagaras <260.7> i Bukarest <374.9>; (Fagaras po raz drugi, bo 260.7 < 287.8)

Zdejmij Fagaras <260.7>;
Włóż Sibiu <325> i Pitesti <370.5>; (nie wkładaj Urziceni, Bucharest i Hirsova, bo ich odległości przez Fagaras są większe od uprzednio obliczonych)

Zdejmij Hirsova <275.7>;
Włóż Bucharest <425> i Eforie <366.3>;

Zdejmij Fagaras <287.8> i kontynuuj, bo 287.8 != 260.7;

Zdejmij Sibiu <325>;
...