Dikstra's Algorithmus mit Radix-Heaps

Einstufige Radix-Heaps:

Menge von $B=\left\lceil \log_2(C+1)\right\rceil + 2$ Buckets (jeder Bucket als doppelt verkettete Liste implementiert). Jeder Bucket hat Größe size, mit

$$\text{size}(i) = \left\{ \begin{array} {ll} 1 & \text{f\um... ...2,\ldots,B-1\\ nC+1 & \text{f\uml {u}r } i=B\end{array}\right.$$

Beobachtung:

$$\sum_{i=1}^{j-1} \text{size}(i) \geq \min\{\text{size}(j),C+1\} \text{ f\uml {u}r } j=2,\ldots,B$$

Wir ordnen den Buckets Intervalle zu, indem wir für jeden Bucket i eine obere Intervallgrenze u(i) angeben. Das Intervall für Bucket i ist dann [u(i-1)+1,u(i)]. Setze zu Beginn u(0):=-1. Die u(i) ändern sich im Algorithmus, die $\text{size}(i)$ bleiben konstant. Zu Beginn:

$$\begin{array} {ll} \text{u}(i) & := 2^{i-1}-1 \text{ f\uml ... ...ntervalls:}\\ u(i)-u(i-1) \leq \text{size}(i)\end{array}\right.$$

• Initialisierung: Einfügen aller Schlüssel in die Buckets: Durchlaufe, für Schlüssel k, die Buckets B, B-1, $\ldots$ bis wir Bucket j finden mit u(j)<k. Füge k in Bucket j+1 ein. Kosten: $n \cdot \log C$.
• DecreaseKey : Wie bei Insert, beginne Suche mit momentanem Bucket des Schlüssels. Kosten für alle DecreaseKey Operationen: $\mathcal{O}(1)$ pro DecreaseKey $+ \mathcal{O}(n \log C)$.
• DeleteMin : Suche von links den ersten nicht leeren Bucket j. Falls j=1 ist alles ok (wegen size(1)=1). Falls $j \geq 2$: Suche minimales Element v im Bucket j (v wird als FindMin

  zurückgegeben und aus der Priority Queue gelöscht), verteile alle anderen Elemente im Bucket j auf die Buckets $1,\ldots,j-1$, nachdem die u(i)'s, wie folgt, aktualisiert wurden:
  u$(0):=\text{dis}[v]-1$
  u$(1):=\text{dis}[v]$
  u$(i):=\min\{$u$(i-1)+\text{size}(i),$u$(j)\} \text{ f\uml {u}r } i=2,\ldots,j-1$

  
  
  

  Kosten für alle DeleteMins : $\mathcal{O}(\log C)$ pro DeleteMin + $\mathcal{O}(n\log C)$.

Gesamtkosten für Dijkstra's Algorithmus mit einstufigen Radix-Heaps damit:

$$\mathcal{O}(m+m+n \log C+n \log C+n \log C)=\mathcal{O}(m+n \log C)$$

Verbesserungen:

1.

zweistufige Heaps:

2.

mehrstufige Heaps (+Fibonacci-Heaps):

Literatur: Akuja, Mehlhorn, Orlin, Tarjan; Faster Algorithms for the Shortest Path Problem. J ACM 37(1990), S. 213-223).