Bellman-Ford algoritması, ağırlıklı (weighted) graf içindeki en kısa yol problemini çözmek için kullanılan bir algoritmadır. En kısa yol problemi, bir başlangıç noktasından hedef noktaya en kısa yolun bulunması problemidir. Bellman-Ford algoritması, olası tüm yol kombinasyonlarını inceleyerek en kısa yolu bulur. Bu algoritma negatif ağırlıklı kenarlara sahip graf gibi durumları da ele alabilir, bu nedenle Dijkstra algoritmasından farklı olarak daha genel bir kullanıma sahiptir.

Bellman-Ford algoritmasının çalışma prensibi şu şekildedir:

1. Başlangıç noktasına uzaklıkları sonsuz, kendisine olan uzaklığı ise 0 olarak ayarla.
2. Tüm kenarları ve ağırlıkları gözden geçir ve her bir kenar için başlangıç noktasından gidilen bir yolun, hedef noktaya olan uzaklığını güncelle.
3. Bu işlemi toplam düğüm sayısı - 1 defa tekrarla. N defa yapılmasının sebebi, en kısa yolun en fazla N-1 kenardan geçebileceği gerçeğidir. N defadan sonra hala daha kısa yollar güncellenebiliyorsa, bu grafın negatif ağırlıklı döngüye sahip olduğunu gösterir.

Dijkstra algoritması, pozitif ağırlıklı graf veya kenarlarda en kısa yolu bulmak için hızlı bir şekilde çalışan bir algoritmadır. Her adımda en küçük uzaklığa sahip düğüm seçilerek işlem yapar. Diğer yandan, Bellman-Ford algoritması negatif veya pozitif ağırlıklı graf ve kenarlarda kullanılabilir ve daha genel bir kullanıma sahiptir. Tüm kenarları ve ağırlıkları adım adım gözden geçirerek en kısa yolu bulur, ancak her adımda tüm kenarları incelediği için daha fazla zaman gerektirebilir. Bu nedenle Dijkstra genellikle daha hızlı çalışırken, Bellman-Ford algoritması daha geniş bir problem yelpazesini ele alabilir ve negatif ağırlıklı graf veya kenarları da işleyebilir.

Karmaşıklık

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

GoLang’de Bellman–Ford Algoritması uygulaması:

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)
		}
	}
}

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

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]

Programın çalışır haline şuradan erişilebilir.

Kaynaklar

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