Bellman-Ford-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
K (Kategorien)
(Link und Beispiel (noch nicht gut, darum auskommentiert))
 
(10 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
<div class="thumb tright">
{{Thumbnailbox
<div class="thumbinner">
|INHALT={{Beispielgraph/gerichtet|BD=red|BDWT=-5}}
{{#mermaid:graph LR
|CAPTION=Ein Beispielgraph, in dem eine Kante negatives Gewicht hat; diese Kante ist farblich hervorgehoben.
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- -5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
 
linkStyle 3 stroke:red;
}}
}}
<div class="thumbcaption">Ein Beispielgraph, in dem eine Kante negatives Gewicht hat; diese Kante ist farblich hervorgehoben.</div>
</div>
</div>


Der [[Bellman-Ford-Algorithmus]] ist ein [[Algorithmus]], der kürzeste Wege in einem [[Graph|Graphen]] findet. Anders als der [[Dijkstra-Algorithmus]] kann der Bellman-Ford-Algorithmus jedoch auch mit negativen Kantengewichten umgehen.
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==
==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]] 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.
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==
==Der Algorithmus==
Zeile 37: Zeile 20:
Der Algorithmus läuft folgendermaßen ab:
Der Algorithmus läuft folgendermaßen ab:


* Zu Beginn des Algorithmus wird für jeden Knoten die Distanz auf <math>\infty</math> gesetzt, außer für <code>s</code>, dessen Distanz auf 0 gesetzt wird.
# 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.
* Dann wird <code>n-1</code> Mal durch alle Kanten durchiteriert und für jede Kante <code>x—y</code> Folgendes geprüft:
# Wiederhole <code>n-1</code> Mal:
** Ist Distanz <code>s—x</code> + Kante <code>x—y</code> < Distanz <code>s—y</code>?
## Prüfe für jede Kante <code>x—y</code>:
*** Falls ja, setze Distanz <code>s—y</code> := Distanz <code>s—x</code> + Kante <code>x—y</code> Vorgänger von <code>y</code> := <code>x</code>
### Ist <code>Distanz[x]</code> + Kantenlänge <code>x—y</code> < <code>Distanz[y]</code>?
* Zuletzt wird nochmal durch alle Kanten durchiteriert und für jede Kante <code>x—y</code> dieselbe Bedingung geprüft:
#### Falls ja, setze <code>Distanz[y]</code> := <code>Distanz[x]</code> + Kante <code>x—y</code>…
** Ist Distanz <code>s—x</code> + Kante <code>x—y</code> < Distanz <code>s—y</code>?
#### … und setze <code>Vorgänger[y]</code> := <code>x</code>
*** Falls ja, ...?
# 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 ==
== Weblinks ==


* [https://visualgo.net/en/sssp Visualisierung auf VisuAlgo.net 🇬🇧]
* {{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:Graphen]]
[[Kategorie:Algorithmen]]
[[Kategorie:Algorithmen]]

Aktuelle Version vom 12. November 2024, 14:43 Uhr

Ein Beispielgraph, in dem eine Kante negatives Gewicht hat; diese Kante ist farblich hervorgehoben.

Der Bellman-Ford-Algorithmus ist ein Algorithmus, der kürzeste Wege in einem gerichteten 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 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 G mit n Knoten
  • ein Startknoten s, von dem aus alle kürzesten Wege berechnet werden sollen

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

Der Algorithmus läuft folgendermaßen ab:

  1. Zu Beginn des Algorithmus wird für jeden Knoten k die Distanz[k] auf und der Vorgänger[k] auf null gesetzt, außer für s, dessen Distanz auf 0 gesetzt wird.
  2. Wiederhole n-1 Mal:
    1. Prüfe für jede Kante x—y:
      1. Ist Distanz[x] + Kantenlänge x—y < Distanz[y]?
        1. Falls ja, setze Distanz[y] := Distanz[x] + Kante x—y…
        2. … und setze Vorgänger[y] := x
  3. Zuletzt wird nochmal durch alle Kanten durchiteriert und für jede Kante x—y dieselbe Bedingung geprüft:
    1. Ist Distanz[x] + Kante x—y < Distanz[y]?
      1. 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.
      2. Falls nein, sind die kürzesten Wege gefunden und die Distanzen und Vorgänger werden zurückgegeben.

Beispiel

🕳
Lückenhaft

In diesem Artikel oder Abschnitt fehlen noch wichtige Informationen.

Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.

Weblinks

Abgerufen von „https://wiki.kah.gs/index.php?title=Bellman-Ford-Algorithmus&oldid=6776“