Dijkstra-Algorithmus (Routing)

Ein Link-State-Algorithmus, der iterativ den kürzesten Pfadbaum (Minimal Spanning Tree) von einem Quellknoten $u$ zu allen anderen Knoten berechnet.

Problem: Minimale Spannbäume
Prozedur:

1. Init: Startknoten in Menge $N^{\prime }$, Kosten zu direkten Nachbarn setzen, andere auf $\mathrm{\infty }$.
2. Loop: Wähle Knoten $w$ außerhalb $N^{\prime }$ mit geringsten Kosten $D(w)$.
3. Update: Für alle Nachbarn $v$ von $w$: Prüfe, ob der Weg über $w$ günstiger ist: $D(v)=min(D(v),D(w)+c(w,v))$.
4. Wiederhole bis alle Knoten in $N^{\prime }$ sind .