Der Bellman-Ford-Algorithmus ist ein Algorithmus zur Lösung des Kürzeste-Wege-Problems in einem gewichteten Graphen. Das Problem des kürzesten Weges ist das Problem, den kürzesten Weg von einem Startpunkt zu einem Ziel zu finden. Der Bellman-Ford-Algorithmus findet den kürzesten Weg, indem er alle möglichen Wegkombinationen untersucht. Dieser Algorithmus kann auch Situationen wie Diagramme mit negativ gewichteten Kanten verarbeiten, sodass er im Gegensatz zu Dijkstras Algorithmus allgemeiner einsetzbar ist.

Das Funktionsprinzip des Bellman-Ford-Algorithmus ist wie folgt:

1. Stellen Sie die Abstände zum Startpunkt auf Unendlich und den Abstand zu sich selbst auf 0 ein.
2. Überprüfen Sie alle Kanten und Gewichte und aktualisieren Sie die Entfernung eines Pfads vom Startpunkt zum Zielpunkt für jede Kante.
3. Wiederholen Sie diesen Vorgang für die Gesamtzahl der Knoten – 1 Mal. Der Grund dafür, dass dies N-mal durchgeführt wird, ist die Tatsache, dass der kürzeste Weg durch höchstens N-1 Kanten verlaufen kann. Wenn kürzere Pfade nach n-Zeiten immer noch aktualisiert werden können, weist dies darauf hin, dass der Graph eine negativ gewichtete Schleife aufweist.

Dijkstras Algorithmus ist ein schnell laufender Algorithmus zum Finden des kürzesten Pfades auf positiv gewichteten Graphen oder Kanten. Bei jedem Schritt wird der Knoten mit dem kleinsten Abstand ausgewählt und in Betrieb genommen. Andererseits kann der Bellman-Ford-Algorithmus auf negativ oder positiv gewichtete Graphen und Kanten angewendet werden und ist allgemeiner einsetzbar. Es findet den kürzesten Weg, indem es Schritt für Schritt alle Kanten und Gewichte durchgeht. Es kann jedoch mehr Zeit in Anspruch nehmen, da bei jedem Schritt alle Kanten untersucht werden. Während Dijkstra im Allgemeinen schneller arbeitet, kann der Bellman-Ford-Algorithmus daher ein breiteres Spektrum an Problemen bewältigen und auch negativ gewichtete Diagramme oder Kanten verarbeiten.

Komplexität

• Worst-case performance O(|V||E|)
• Best-case performance O(|E|)
• Worst-case space complexity O(|V|)

Implementierung des Bellman-Ford-Algorithmus in GoLang:

package main

import (
	"fmt"
	"math"
)

type Edge struct {
	Source int
	Target int
	Weight int
}

func BellmanFord(edges []Edge, vertexCount int, start int) ([]int, []int) {
	distances := make([]int, vertexCount)
	predecessors := make([]int, vertexCount)

	for i := range distances {
		distances[i] = math.MaxInt32
	}
	distances[start] = 0

	for i := 1; i < vertexCount; i++ {
		for _, edge := range edges {
			if distances[edge.Source]+edge.Weight < distances[edge.Target] {
				distances[edge.Target] = distances[edge.Source] + edge.Weight
				predecessors[edge.Target] = edge.Source
			}
		}
	}

	for _, edge := range edges {
		if distances[edge.Source]+edge.Weight < distances[edge.Target] {
			fmt.Println("Negative cycle detected. Bellman-Ford algorithm cannot be applied.")
			return nil, nil
		}
	}

	return distances, predecessors
}

func main() {
	vertexCount := 5
	edges := []Edge{
		{0, 1, 2},
		{0, 2, 4},
		{1, 2, 1},
		{1, 3, 7},
		{2, 4, 3},
		{3, 4, 1},
	}

	startNode := 0
	distances, predecessors := BellmanFord(edges, vertexCount, startNode)

	if distances != nil {
		fmt.Println("Shortest distances from node", startNode)
		for i, distance := range distances {
			fmt.Printf("Node %d: Distance %d, Path: ", i, distance)
			path := []int{}
			for at := i; at != startNode; at = predecessors[at] {
				path = append([]int{at}, path...)
			}
			path = append([]int{startNode}, path...)
			fmt.Println(path)
		}
	}
}

Wenn das Programm ausgeführt wird, sieht die Ausgabe wie folgt aus.

Shortest distances from node 0
Node 0: Distance 0, Path: [0]
Node 1: Distance 2, Path: [0 1]
Node 2: Distance 3, Path: [0 1 2]
Node 3: Distance 9, Path: [0 1 2 4 3]
Node 4: Distance 6, Path: [0 1 2 4]

Auf die laufende Version des Programms kann hier zugegriffen werden.

Ressourcen

• https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
• https://www.baeldung.com/cs/bellman-ford