Der Algorithmus von Johnson

Definition: Sei $d:A\rightarrow \mathbbm{R}$ eine Distanzfunktion. Eine Abbildung
$r:V\rightarrow \mathbbm{R}$ heißt

Rekalibrierung , falls gilt:

$$\forall (u,v)\in A : r(u) + d(u,v) \geq r(v)$$

Beobachtung: Sei r eine Rekalibrierung (für d). Setze d'(u,v):=d(u,v)+r(u)-r(v). Dann gilt:

$$d'(u,v) \geq 0$$

Sei $u=v_0\rightarrow \cdots \rightarrow v_1=v$ ein Pfad. Dann ist:

$$d\text{-L\uml {a}nge} =\sum_{i=1}^{r}d(v_i,v_{i-1})$$

Demnach ist:

$$\begin{split} d'\text{-L\uml {a}nge } & = \sum_{i=1}^{r}d'(v... ...\\ & = \sum_{i=1}^{r}d(v_i,v_{i-1})+r(v_r)+r(v_0)\\ \end{split}$$

Also ist ein d-kürzester Pfad von u (v₀) nach v (v_r) auch ein d'-kürzester Pfad und umgekehrt. Man kann jetzt mit Hilfe von d' beliebige Algorithmen (Dijkstra, Floyd, etc.) anwenden.

Berechnung einer Rekalibrierung: a-Algorithmus.

$\parbox{50mm}{F\uml {u}ge einen neuen Knoten $s$\space hinzu und verb... ... jedem anderen Knoten $v\in V$\space durch eine Kante der L\uml {a}nge $0$.\\ }$

Berechne sssp von s nach allen anderen Knoten $v\in V$ (z.B. mit Floyd). Sei r(v) die dadurch berechnete Entfernung von s zu $v\in V$. Dann r Rekalibrierung, denn es gilt:

$$r(u)+d(u,v)\geq r(v)$$