Bellman Ford's Algorithm

Bellman-Ford algoritmi — bu bitta boshlang'ich manbadan boshqa barcha cho'qqilarga olib boruvchi eng qisqa yo'lni topish algoritmidir. U Dijkstra algoritmiga juda o'xshash, ammo Dijkstradan farqli ravishda qirralari manfiy og'irliklarga (negative weights) ega bo'lgan graflarda ham to'g'ri ishlay oladi.

Haqiqiy hayotda manfiy og'irlikdagi qirralar qayerda uchraydi?

Manfiy vaznli qirralar dastlab g'alati yoki amaliyotda keraksizdek tuyulishi mumkin, biroq ular real dunyodagi juda ko'p hodisalarni, masalan, moliyaviy pul oqimlari (foyda/zarar), kimyoviy reaksiyalarda issiqlik ajralishi yoki yutilishi kabilarni ajoyib tarzda ifodalaydi.

Masalan, bitta kimyoviy modda A dan boshqa kimyoviy modda B ga o'tishning turli yo'llari mavjud bo'lsa, har bir oraliq reaksiya issiqlik chiqarishi (ekzotermik) yoki issiqlik yutishi (endotermik) mumkin.

Agar biz minimal energiya talab qiladigan reaksiyalar ketma-ketligini topmoqchi bo'lsak, issiqlik yutilishini manfiy og'irlik, ajralishini esa musbat og'irlik sifatida hisobga olishimiz kerak bo'ladi.

Nega manfiy og'irliklarda ehtiyot bo'lish lozim?

Manfiy vaznli qirralar manfiy vaznli sikllarni (negative weight cycles) hosil qilishi mumkin. Ya'ni, sikl bo'ylab aylanib asl boshlangan nuqtaga qaytib kelganda, umumiy bosib o'tilgan yo'l masofasi yanada kamayib (manfiy tomonga cheksiz kamayib) boradi.

Manfiy vaznli sikllar eng qisqa yo'lni qidirishda noto'g'ri natijaga olib kelishi mumkin

Bunday sikllarni aniqlay olmaydigan eng qisqa yo'l algoritmlari (masalan, Dijkstra algoritmi) xato natija beradi, chunki ular ushbu sikl bo'ylab qayta-qayta aylanib, yo'l uzunligini cheksiz ravishda kamaytirishga urinadi.

Bellman-Ford algoritmi qanday ishlaydi?

Bellman-Ford algoritmi dastlab boshlang'ich cho'qqidan boshqa barcha cho'qqilarga bo'lgan masofani haddan tashqari yuqori (cheksiz ∞) deb baholashdan boshlaydi. So'ngra oldingi baholangan masofalardan qisqaroq bo'lgan yangi yo'llarni topish orqali ushbu baholarni iterativ ravishda bo'shashtiradi (relaksatsiya qiladi / relaxes).

Ushbu jarayonni barcha cho'qqilar uchun V - 1 marta takrorlash orqali natija eng maqbul (optimal) bo'lishi kafolatlanadi.

Bellman-Ford algoritmi: 1-qadam

Bellman-Ford algoritmi: 2-qadam

Bellman-Ford algoritmi: 3-qadam

[!TIP] Eslatma: Yo'lni bo'shashtirish (relaksatsiya qilish) uchun (U, V) qirrasida quyidagi shart tekshiriladi: agar distance(U) + edge_weight(U, V) < distance(V) bo'lsa, unda distance(V) = distance(U) + edge_weight(U, V) qiymati o'rnatiladi.

Bellman-Ford algoritmi: 4-qadam

Bellman-Ford algoritmi: 5-qadam

Bellman-Ford algoritmi: 6-qadam

Bellman-Ford soxta kodi

Biz har bir cho'qqigacha bo'lgan masofani saqlab borishimiz kerak. Buning uchun V o'lchamli massivdan foydalanamiz, bu yerda V — grafdagi cho'qqilar soni.

Shuningdek, nafaqat eng qisqa masofani bilish, balki eng qisqa yo'lning o'zini ham tiklay olish maqsadida har bir cho'qqining masofasini oxirgi marta yangilagan o'tmishdosh cho'qqini (previous) qayd etib boramiz.

Algoritm tugagach, mo'ljallangan manzil cho'qqisidan boshlang'ich cho'qqiga qarab orqaga qarab qaytish (backtrack) orqali aniq yo'l topiladi.

function bellmanFord(G, S)
    for each vertex V in G:
        distance[V] <- infinity
        previous[V] <- NULL
    distance[S] <- 0

    // Qirralarni |V| - 1 marta relaksatsiya qilish
    for i from 1 to |V| - 1:
        for each edge (U, V) in G:
            tempDistance <- distance[U] + edge_weight(U, V)
            if tempDistance < distance[V]:
                distance[V] <- tempDistance
                previous[V] <- U

    // Manfiy vaznli siklni tekshirish
    for each edge (U, V) in G:
        if distance[U] + edge_weight(U, V) < distance[V]:
            Error: "Grafda manfiy vaznli sikl mavjud!"

    return distance[], previous[]

Bellman-Ford va Dijkstra algoritmlarining farqi

Tuzilishi jihatidan Bellman-Ford va Dijkstra algoritmlari juda o'xshashdir. Biroq Dijkstra algoritmi har doim faqat joriy cho'qqining bevosita eng yaqin qo'shnilariga qarasa (ochko'z yondashuv / greedy approach), Bellman-Ford har bir iteratsiyada grafdagi barcha qirralarni to'liq aylanib chiqadi.

Bellman-Ford algoritmi va Dijkstra algoritmining qiyosiy taqqoslanishi

Dasturiy namunalar

// Go tilida Bellman-Ford algoritmi
package main

import (
	"fmt"
	"math"
)

type Edge struct {
	u, v, w int
}

type Graph struct {
	V, E  int
	edges []Edge
}

func NewGraph(v, e int) *Graph {
	return &Graph{
		V:     v,
		E:     e,
		edges: make([]Edge, 0, e),
	}
}

func (g *Graph) AddEdge(u, v, w int) {
	g.edges = append(g.edges, Edge{u: u, v: v, w: w})
}

func (g *Graph) BellmanFord(src int) {
	dist := make([]float64, g.V)
	for i := range dist {
		dist[i] = math.Inf(1)
	}
	dist[src] = 0

	// 1-bosqich: Qirralarni |V| - 1 marta relaksatsiya qilish
	for i := 1; i <= g.V-1; i++ {
		for _, edge := range g.edges {
			u, v, w := edge.u, edge.v, float64(edge.w)
			if !math.IsInf(dist[u], 1) && dist[u]+w < dist[v] {
				dist[v] = dist[u] + w
			}
		}
	}

	// 2-bosqich: Manfiy vaznli siklni aniqlash
	for _, edge := range g.edges {
		u, v, w := edge.u, edge.v, float64(edge.w)
		if !math.IsInf(dist[u], 1) && dist[u]+w < dist[v] {
			fmt.Println("Grafda manfiy vaznli sikl aniqlandi!")
			return
		}
	}

	// Natijani chop etish
	fmt.Println("Cho'qqi\tManbadan masofa")
	for i := 0; i < g.V; i++ {
		fmt.Printf("%d\t\t%.0f\n", i, dist[i])
	}
}

func main() {
	g := NewGraph(5, 5)

	g.AddEdge(0, 1, 5)
	g.AddEdge(0, 2, 4)
	g.AddEdge(1, 3, 3)
	g.AddEdge(2, 1, 6)
	g.AddEdge(3, 2, 2)

	g.BellmanFord(0)
}

Bellman-Ford algoritmining murakkabligi

Vaqt murakkabligi

Xotira murakkabligi

Algoritmning xotira murakkabligi O(V) ga teng (masofalar va o'tmishdoshlar massivlari uchun).

Bellman-Ford algoritmining qo'llanilishi

1. Tarmoq marshrutlash protokollarida (Routing Protocols): Masofani o'lchovchi marshrutlash protokollarida (masalan, RIP — Routing Information Protocol) eng maqbul yo'llarni hisoblashda.
2. Manfiy sikllarni aniqlashda: Moliyaviy arbitraj (valyuta ayirboshlash bo'yicha daromad olish halqalarini qidirish) tizimlarida.
3. Manfiy og'irliklarga ega graflarda eng qisqa yo'lni topishda.