Quelltext der Seite Bellman-Ford-Algorithmus

{{Thumbnailbox
|INHALT={{Beispielgraph/gerichtet|BD=red|BDWT=-5}}
|CAPTION=Ein Beispielgraph, in dem eine Kante negatives Gewicht hat; diese Kante ist farblich hervorgehoben.
}}

Der [[Bellman-Ford-Algorithmus]] ist ein [[Algorithmus]], der [[Wegfindung|kürzeste Wege]] in einem gerichteten [[Graph|Graphen]] findet. Anders als der [[Dijkstra-Algorithmus]] kann der Bellman-Ford-Algorithmus jedoch auch mit negativen Kantengewichten umgehen.

==Das Problem==

Betrachten wir den nebenstehenden Beispielgraphen, in dem eine Kante negatives Gewicht hat. Der kürzeste Weg von A nach D führt über B und hat die Länge -2. Der Dijkstra-Algorithmus würde aber den Weg über C präferieren, der die Länge 3 hat. Der Dijkstra-Algorithmus ist nämlich [[Greedy-Algorithmus|greedy]] und betrachtet immer nur die nächstbeste Kante mit minimalem Gewicht. Bei Graphen mit ausschließlich positiven Kantengewichten ist das kein Problem, da die Gesamtlänge eines Weges immer nur größer werden kann. Bei Graphen, in denen auch negative Kantengewichte vorkommen, dagegen schon, da es hier auch vorteilhaft sein kann, zunächst größere Kantengewichte in Kauf zu nehmen, wenn diese später durch negative Kantengewichte ausgeglichen werden können.

==Der Algorithmus==
Gegeben seien:

* ein Graph <code>G</code> mit <code>n</code> Knoten
* ein Startknoten <code>s</code>, von dem aus alle kürzesten Wege berechnet werden sollen

Zu jedem Knoten im Graph wird nun seine Distanz zum Startknoten <code>s</code> gespeichert sowie der direkte Vorgänger auf dem Weg zu <code>s</code>. Durch die Vorgänger kann man sich so den kürzesten Weg zu <code>s</code> erarbeiten.

Der Algorithmus läuft folgendermaßen ab:

# Zu Beginn des Algorithmus wird für jeden Knoten <code>k</code> die <code>Distanz[k]</code> auf <math>\infty</math> und der <code>Vorgänger[k]</code> auf <code>[[null]]</code> gesetzt, außer für <code>s</code>, dessen Distanz auf 0 gesetzt wird.
# Wiederhole <code>n-1</code> Mal:
## Prüfe für jede Kante <code>x—y</code>:
### Ist <code>Distanz[x]</code> + Kantenlänge <code>x—y</code> < <code>Distanz[y]</code>?
#### Falls ja, setze <code>Distanz[y]</code> := <code>Distanz[x]</code> + Kante <code>x—y</code>…
#### … und setze <code>Vorgänger[y]</code> := <code>x</code>
# Zuletzt wird nochmal durch alle Kanten durchiteriert und für jede Kante <code>x—y</code> dieselbe Bedingung geprüft:
## Ist <code>Distanz[x]</code> + Kante <code>x—y</code> < <code>Distanz[y]</code>?
### Falls ja, dann enthält der Graph einen Kreis negativer Länge. In diesem Fall können durch wiederholtes Durchlaufen dieses Kreises beliebig kurze Wege erzeugt werden und es kann keine kürzesten Wege geben.
### Falls nein, sind die kürzesten Wege gefunden und die Distanzen und Vorgänger werden zurückgegeben.

== Beispiel ==
<!--
=== Ohne einen Kreis negativer Länge ===

Betrachten wir den oben abgebildeten Graphen mit der negativen Kante.

{| class="wikitable
|-
! Schritt
! <code>distance</code> 
! <code>previous</code> 
! Wdh.-Zähler
! <math>v</math> 
! <math>u \rightarrow v</math> 
|-
| 1
| [A:&nbsp;0, B:&nbsp;<math>\infty</math>, C:&nbsp;<math>\infty</math>, D:&nbsp;<math>\infty</math>, E:&nbsp;<math>\infty</math>] 
| [A:&nbsp;null, B:&nbsp;null, C:&nbsp;null, D:&nbsp;null, E:&nbsp;null] 
| 
| 
| 
|-
| 2
| 
| 
| 0 
| 
|  
|-
| 2.1 
| 
| 
| 
| 
| <math>A\rightarrow B</math>  
|-
| 2.1.1 
| [A:&nbsp;0, B:&nbsp;3, C:&nbsp;<math>\infty</math>, D:&nbsp;<math>\infty</math>, E:&nbsp;<math>\infty</math>] 
| 
| 
| 
|  
|-
| 12 
| 
| [A:&nbsp;null, B:&nbsp;A, C:&nbsp;null, D:&nbsp;null, E:&nbsp;null] 
| 
| 
|  
|-
| 9 
| 
| 
| 
| 
| <math>A\rightarrow C</math>  
|-
| 11 
| [A:&nbsp;0, B:&nbsp;3, C:&nbsp;1, D:&nbsp;<math>\infty</math>, E:&nbsp;<math>\infty</math>] 
| 
| 
| 
|  
|-
| 12 
| 
| [A:&nbsp;null, B:&nbsp;A, C:&nbsp;A, D:&nbsp;null, E:&nbsp;null] 
| 
| 
|  
|-
| 9 
| 
| 
| 
| 
| <math>B\rightarrow C</math>  
|-
| 9 
| 
| 
| 
| 
| <math>B\rightarrow D</math>  
|-
| 11 
| [A:&nbsp;0, B:&nbsp;3, C:&nbsp;1, D:&nbsp;-2, E:&nbsp;<math>\infty</math>] 
| 
| 
| 
|  
|-
| 12 
| 
| [A:&nbsp;null, B:&nbsp;A, C:&nbsp;A, D:&nbsp;B, E:&nbsp;null] 
| 
| 
|  
|-
| 9 
| 
| 
| 
| 
| <math>B\rightarrow E</math>  
|-
| 11 
| [A:&nbsp;0, B:&nbsp;3, C:&nbsp;1, D:&nbsp;-2, E:&nbsp;4] 
| 
| 
| 
|  
|-
| 12 
| 
| [A:&nbsp;null, B:&nbsp;A, C:&nbsp;A, D:&nbsp;B, E:&nbsp;B] 
| 
| 
|  
|-
| 9 
| 
| 
| 
| 
| <math>C\rightarrow D</math>  
|-
| 9 
| 
| 
| 
| 
| <math>C\rightarrow E</math>  
|-
| 8 
| 
| 
| 1 
| 
|  
|-
| 9 
| 
| 
| 
| 
| <math>A\rightarrow B</math>  
|-
| 9 
| 
| 
| 
| 
| <math>A\rightarrow C</math>  
|-
| 9 
| 
| 
| 
| 
| <math>B\rightarrow C</math>  
|-
| 9 
| 
| 
| 
| 
| <math>B\rightarrow D</math>  
|-
| 9 
| 
| 
| 
| 
| <math>B\rightarrow E</math>  
|-
| 9 
| 
| 
| 
| 
| <math>C\rightarrow D</math>  
|-
| 9 
| 
| 
| 
| 
| <math>C\rightarrow E</math>  
|}

Am Ende des hier dargestellten Ablaufes terminiert der Algorithmus und gibt <code>distance = [A: 0, B: 3, C: 1, D: -2, E: 4]</code>, <code>previous = [A: [[null]], B: A, C: A, D: B, E: B]</code> als Ergebnis zurück.
-->
{{Lückenhaft}}

== Weblinks ==

* {{VisuAlgo|en/sssp|Der Bellman-Ford-Algorithmus visualisiert}}
* [https://algorithms.discrete.ma.tum.de/graph-algorithms/spp-bellman-ford/index_de.html Erklärung und interaktives Beispiel der TU München]
{{Navigationsleiste Graphalgorithmen}}
[[Kategorie:Graphen]]
[[Kategorie:Algorithmen]]