Informatik Algorithmen – Bellman-Ford und negative Kanten

Rückseite

Er findet kürzeste Pfade von einem Startknoten zu allen anderen Knoten in Graphen mit negativ gewichteten Kanten.

Rückseite

Dijkstra geht davon aus, dass ein einmal festgelegter kürzester Pfad nie kürzer wird – negative Kanten verletzen diese Annahme.

Rückseite

Prüfen, ob der Pfad über eine Kante (u,v) kürzer ist als der aktuell bekannte Pfad nach v, und Distanz entsprechend aktualisieren.

Rückseite

Genau |V| - 1 Iterationen, wobei |V| die Anzahl der Knoten ist.

Rückseite

Ein kürzester Pfad ohne Zyklen enthält maximal |V| - 1 Kanten; nach so vielen Iterationen sind alle solchen Pfade gefunden.

Rückseite

Nach |V| - 1 Iterationen wird eine weitere ausgeführt: verkürzt sich noch eine Distanz, existiert ein negativer Zyklus.

Rückseite

O(|V| · |E|), da |V| - 1 Iterationen jeweils alle |E| Kanten relaxieren.

Rückseite

Startknoten erhält Distanz 0, alle anderen Knoten erhalten Unendlich (∞).

Rückseite

Ein Zyklus, dessen Summe der Kantengewichte negativ ist – kürzeste Pfade sind dann nicht wohldefiniert.

Rückseite

Nur wenn keine negativen Kanten existieren; eine ungerichtete negative Kante erzeugt sofort einen negativen 2-Zyklus.

Rückseite

Falls dist[u] + w < dist[v], wird dist[v] auf dist[u] + w gesetzt und Vorgänger[v] auf u aktualisiert.

Rückseite

Wenn in einer kompletten Iteration keine Distanz mehr aktualisiert wurde – alle kürzesten Pfade sind dann final.

Rückseite

Modellierung von Gewinnen (negative Kosten), Währungsarbitrage oder zeitliche Constraints in Scheduling-Problemen.

Rückseite

Über das Vorgänger-Array vom Zielknoten rückwärts zum Startknoten folgen und die Reihenfolge umkehren.

Rückseite

SPFA (Shortest Path Faster Algorithm) nutzt eine Queue und relaxiert nur Knoten, deren Distanz sich geändert hat – oft schneller in der Praxis.