DSA Bellman-Ford

Bellman-Ford algoritmi

Bellman-Ford algoritmi bir yoki bir nechta manfiy qirra vazniga ega yo‘naltirilgan grafda manba cho‘qqidan boshqa barcha cho‘qqilargacha eng qisqa yo‘llarni topish uchun eng mos keladi.

U buni qisqaroq yo‘llar bor-yo‘qligini aniqlash maqsadida grafdagi barcha qirralarni grafdagi cho‘qqilar soniga (minus 1) teng marta qayta-qayta tekshirish orqali amalga oshiradi.

Bellman-Ford algoritmidan xuddi Dijkstra algoritmi singari musbat qirrali graflar (yo‘naltirilgan va yo‘naltirilmagan) uchun ham foydalanish mumkin, ammo bunday hollarda Dijkstra algoritmi afzal ko‘riladi, chunki u tezroq.

Manfiy sikllari bor grafda Bellman-Ford algoritmidan foydalanish eng qisqa yo‘llar natijasini bermaydi, chunki manfiy siklda har doim yana bir marta aylanib, qisqaroq yo‘l olishimiz mumkin.

Manfiy sikl — bu aylana bo‘ylab qayta-qayta yurish mumkin bo‘lgan va qirra vaznlari yig‘indisi manfiy bo‘lgan yo‘l.

Yaxshiyamki, Bellman-Ford algoritmini manfiy sikllar mavjudligini ishonchli aniqlaydigan va bu haqda xabar beradigan qilib amalga oshirish mumkin.

Yuqoridagi Bellman-Ford algoritmi animatsiyasi faqat qirrani tekshirish masofaning yangilanishiga olib kelgan holatlarni ko‘rsatadi, masofa yangilanishiga olib kelmagan boshqa qirra tekshiruvlarini esa ko‘rsatmaydi.

Qo‘lda bajarib ko‘rish

Bellman-Ford algoritmi aslida ancha sodda, chunki u qo‘shnilik matritsasidan foydalanib, barcha qirralarni tekshiradi. Har bir tekshiruv qirraning bir tomonidagi cho‘qqidan shu qirra orqali qirraning boshqa tomonidagi cho‘qqiga borib, qisqaroq masofa hosil qilish mumkinligini aniqlashdan iborat.

Barcha qirralarni bunday tekshirish \(V - 1\) marta bajariladi, bu yerda \(V\) — grafdagi cho‘qqilar soni.

Bellman-Ford algoritmi grafimizning qo‘shnilik matritsasidagi barcha qirralarni 5-1=4 marta mana shunday tekshiradi:

Grafimizda tekshiriladigan dastlabki to‘rtta qirra: A->C, A->E, B->C va C->A. Bu dastlabki to‘rtta qirra tekshiruvi eng qisqa masofalarning hech qanday yangilanishiga olib kelmaydi, chunki bu qirralarning barchasida boshlang‘ich cho‘qqining masofasi cheksiz.

A, B va C cho‘qqilaridan chiquvchi qirralar tekshirilgach, D’dan chiquvchi qirralar tekshiriladi. Boshlang‘ich nuqtaning (D cho‘qqisining) masofasi 0 bo‘lgani uchun A, B va C’ning yangilangan masofalari D cho‘qqisidan chiquvchi qirralarning vaznlariga teng bo‘ladi.

Keyingi tekshiriladigan qirralar E cho‘qqisidan chiquvchi qirralardir va ular B hamda C cho‘qqilarining masofalari yangilanishiga olib keladi.

Endi Bellman-Ford algoritmi barcha qirralarni 1 marta tekshirib chiqdi. Algoritm ishini tugatguncha barcha qirralarni yana 3 marta tekshiradi, chunki Bellman-Ford barcha qirralarni grafdagi cho‘qqilar soni minus 1 marta tekshiradi.

Algoritm barcha qirralarni ikkinchi marta tekshirishni A cho‘qqisidan chiquvchi qirralardan boshlaydi. A->C va A->E qirralarini tekshirish masofalarning yangilanishiga olib kelmaydi.

Keyingi tekshiriladigan qirra — B cho‘qqisidan chiquvchi B->C. Bu D cho‘qqisidan C’gacha masofaning 5-4=1 ga yangilanishiga olib keladi.

Keyingi C->A qirrasini tekshirish A cho‘qqisi uchun masofaning 1-3=-2 ga yangilanishiga olib keladi.

Bellman-Ford algoritmining 2-aylanmasidagi C->A qirrasi tekshiruvi aslida ushbu muayyan graf uchun masofa yangilanishiga olib keladigan oxirgi tekshiruvdir. Algoritm hech qanday masofani yangilamagan holda barcha qirralarni yana 2 marta tekshirishda davom etadi.

Bellman-Ford algoritmida barcha qirralarni \(V-1\) marta tekshirish ko‘pdek tuyulishi mumkin, ammo bu eng qisqa masofalar har doim topilishini kafolatlash uchun shuncha marta bajariladi.

Bellman-Ford algoritmini amalga oshirish

Bellman-Ford algoritmini amalga oshirish Dijkstra algoritmini qanday amalga oshirganimizga juda o‘xshaydi.

Ishni Graph sinfini yaratishdan boshlaymiz; undagi __init__, add_edge va add_vertex metodlari eng qisqa yo‘llarni topish uchun Bellman-Ford algoritmini ishga tushirmoqchi bo‘lgan muayyan grafimizni yaratishda ishlatiladi.

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            #self.adj_matrix[v][u] = weight  # For undirected graph

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

bellman_ford metodi ham Graph sinfi ichida joylashgan. Aynan shu metod Bellman-Ford algoritmini ishga tushiradi.

    def bellman_ford(self, start_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        distances = [float('inf')] * self.size
        distances[start_vertex] = 0

        for i in range(self.size - 1):
            for u in range(self.size):
                for v in range(self.size):
                    if self.adj_matrix[u][v] != 0:
                        if distances[u] + self.adj_matrix[u][v] < distances[v]:
                            distances[v] = distances[u] + self.adj_matrix[u][v]
                            print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")

        return distances

18–19-qatorlar: Boshida boshlang‘ich cho‘qqining o‘zidan tashqari barcha cho‘qqilarning boshlang‘ich cho‘qqidan masofasi cheksiz uzun qilib belgilanadi, boshlang‘ich cho‘qqining o‘zi uchun esa masofa 0 ga tenglanadi.

21-qator: Barcha qirralar \(V-1\) marta tekshiriladi.

22–23-qatorlar: Ikki qavatli for sikli qo‘shnilik matritsasidagi barcha qirralarni tekshiradi. Har bir u cho‘qqisi uchun v cho‘qqilariga boradigan qirralarni tekshiring.

24–26-qatorlar: Agar qirra mavjud bo‘lsa va hisoblangan masofa mavjud masofadan qisqaroq bo‘lsa, shu v cho‘qqisigacha bo‘lgan masofani yangilang.

Muayyan grafimizni initsializatsiya qilish va Bellman-Ford algoritmini ishga tushirish kodini o‘z ichiga olgan to‘liq kod quyidagicha:

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            #self.adj_matrix[v][u] = weight  # For undirected graph

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def bellman_ford(self, start_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        distances = [float('inf')] * self.size
        distances[start_vertex] = 0

        for i in range(self.size - 1):
            for u in range(self.size):
                for v in range(self.size):
                    if self.adj_matrix[u][v] != 0:
                        if distances[u] + self.adj_matrix[u][v] < distances[v]:
                            distances[v] = distances[u] + self.adj_matrix[u][v]
                            print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")

        return distances

g = Graph(5)

g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')

g.add_edge(3, 0, 4)  # D -> A, weight 4
g.add_edge(3, 2, 7)  # D -> C, weight 7
g.add_edge(3, 4, 3)  # D -> E, weight 3
g.add_edge(0, 2, 4)  # A -> C, weight 4
g.add_edge(2, 0, -3) # C -> A, weight -3
g.add_edge(0, 4, 5)  # A -> E, weight 5
g.add_edge(4, 2, 3)  # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2)  # E -> B, weight 2

# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
distances = g.bellman_ford('D')
for i, d in enumerate(distances):
    print(f"Distance from D to {g.vertex_data[i]}: {d}")

Bellman-Ford algoritmida manfiy qirralar

Bellman-Ford algoritmi "eng qisqa yo‘llar"ni topadi, deyish unchalik tushunarli emas, axir manfiy masofalarni qanday chizish yoki tasavvur qilish mumkin? Shuning uchun tushunishni osonlashtirish maqsadida Bellman-Ford yordamida "cheapest (eng arzon) yo‘llar" topiladi, deb aytishimiz mumkin.

Amalda Bellman-Ford algoritmi, masalan, yetkazib berish marshrutlarini topishda yordam berishi mumkin; bunda qirra vaznlari yoqilg‘i va boshqa xarajatlardan shu ikki cho‘qqi orasidagi qirra bo‘ylab yurib ishlab topiladigan pul ayirilganini ifodalaydi.

Shu talqinni hisobga olsak, C->A qirrasidagi -3 vazni C’dan A’ga borishda yoqilg‘i xarajati $5 ekanini va C’dan posilkalarni olib, A’ga yetkazib berganimiz uchun bizga $8 to‘lanishini anglatishi mumkin. Natijada sarflaganimizdan $3 ko‘proq ishlab topamiz. Demak, yuqoridagi grafimizda D->E->B->C->A yetkazib berish marshruti bo‘ylab yurib, jami $2 ishlab topish mumkin.

Bellman-Ford algoritmida manfiy sikllar

Agar grafda aylana bo‘ylab yurish mumkin bo‘lsa va shu aylanadagi qirralar yig‘indisi manfiy bo‘lsa, bizda manfiy sikl bor.

C->A qirrasidagi vaznni -3 dan -9 ga o‘zgartirsak, ikkita manfiy sikl hosil bo‘ladi: A->C->A va A->E->C->A. Bu qirralarni Bellman-Ford algoritmi bilan har safar tekshirganimizda hisoblab, yangilayotgan masofalarimiz tobora kichrayib boraveradi.

Manfiy sikllarning muammosi shundaki, eng qisqa yo‘l mavjud bo‘lmaydi, chunki har doim yana bir marta aylanib, qisqaroq yo‘l olishimiz mumkin.

Shu sababli Bellman-Ford algoritmini manfiy sikllarni aniqlash imkoniyati bilan amalga oshirish foydali.

Bellman-Ford algoritmida manfiy sikllarni aniqlash

Bellman-Ford algoritmi ishga tushirilib, grafdagi barcha qirralar \(V-1\) marta tekshirilgach, barcha eng qisqa masofalar topiladi.

Ammo agar grafda manfiy sikllar bo‘lsa va barcha qirralarni yana bir marta tekshirib chiqsak, bu oxirgi aylanmada kamida bitta qisqaroq masofa topamiz, shunday emasmi?

Shunday qilib, Bellman-Ford algoritmida manfiy sikllarni aniqlash uchun barcha qirralarni \(V-1\) marta tekshirgach, ularni yana bir marta tekshirish kifoya; agar bu oxirgi safar qisqaroq masofa topilsa, manfiy sikl albatta mavjud, degan xulosaga kelishimiz mumkin.

Quyida manfiy sikllarni aniqlash qo‘shilgan bellman_ford metodi keltirilgan; u C->A qirra vazni -9 bo‘lgani sababli manfiy sikllarga ega bo‘lgan yuqoridagi grafda ishlamoqda:

    def bellman_ford(self, start_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        distances = [float('inf')] * self.size
        distances[start_vertex] = 0

        for i in range(self.size - 1):
            for u in range(self.size):
                for v in range(self.size):
                    if self.adj_matrix[u][v] != 0:
                        if distances[u] + self.adj_matrix[u][v] < distances[v]:
                            distances[v] = distances[u] + self.adj_matrix[u][v]
                            print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")

        # Negative cycle detection
        for u in range(self.size):
            for v in range(self.size):
                if self.adj_matrix[u][v] != 0:
                    if distances[u] + self.adj_matrix[u][v] < distances[v]:
                        return (True, None)  # Indicate a negative cycle was found

        return (False, distances)  # Indicate no negative cycle and return distances

30–33-qatorlar: Manfiy sikllar bor-yo‘qligini aniqlash uchun barcha qirralar yana bir marta tekshiriladi.

34-qator: True qaytarilishi manfiy sikl mavjudligini bildiradi va eng qisqa masofalar o‘rniga None qaytariladi, chunki manfiy sikllari bor grafda eng qisqa masofalarni topish ma’noga ega emas (sababi, barcha qirralarni yana bir marta tekshirib, har doim qisqaroq masofa topish mumkin).

36-qator: False qaytarilishi manfiy sikllar yo‘qligini bildiradi va distances qaytarilishi mumkin.

Bellman-Ford algoritmidan yo‘llarni qaytarish

Hozircha biz eng qisqa yo‘llarning umumiy vaznini topmoqdamiz, masalan, Bellman-Ford algoritmini ishga tushirish natijasi "Distance from D to A: -2" ko‘rinishida bo‘ladi.

Ammo har safar qirra relaksatsiya qilinganda har bir cho‘qqining oldingi cho‘qqisini (predecessor) yozib borsak, keyinchalik kodimizda bundan foydalanib, natijani haqiqiy eng qisqa yo‘llar bilan birga chiqarishimiz mumkin. Bu natijada ko‘proq ma’lumot — yo‘l vaznidan tashqari yo‘lning o‘zini ham berishimiz mumkinligini anglatadi: "D->E->B->C->A, Distance: -2".

Ushbu oxirgi kod misoli Bellman-Ford algoritmining shu paytgacha muhokama qilgan barcha narsalarimizni o‘z ichiga olgan to‘liq kodidir: eng qisqa yo‘llar vaznlarini topish, manfiy sikllarni aniqlash va haqiqiy eng qisqa yo‘llarni topish:

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            #self.adj_matrix[v][u] = weight  # For undirected graph

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def bellman_ford(self, start_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        distances = [float('inf')] * self.size
        predecessors = [None] * self.size
        distances[start_vertex] = 0

        for i in range(self.size - 1):
            for u in range(self.size):
                for v in range(self.size):
                    if self.adj_matrix[u][v] != 0:
                        if distances[u] + self.adj_matrix[u][v] < distances[v]:
                            distances[v] = distances[u] + self.adj_matrix[u][v]
                            predecessors[v] = u
                            print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")

        # Negative cycle detection
        for u in range(self.size):
            for v in range(self.size):
                if self.adj_matrix[u][v] != 0:
                    if distances[u] + self.adj_matrix[u][v] < distances[v]:
                        return (True, None, None)  # Indicate a negative cycle was found

        return (False, distances, predecessors)  # Indicate no negative cycle and return distances
    
    def get_path(self, predecessors, start_vertex, end_vertex):
        path = []
        current = self.vertex_data.index(end_vertex)
        while current is not None:
            path.insert(0, self.vertex_data[current])
            current = predecessors[current]
            if current == self.vertex_data.index(start_vertex):
                path.insert(0, start_vertex)
                break
        return '->'.join(path)

g = Graph(5)

g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')

g.add_edge(3, 0, 4)  # D -> A, weight 4
g.add_edge(3, 2, 7)  # D -> C, weight 7
g.add_edge(3, 4, 3)  # D -> E, weight 3
g.add_edge(0, 2, 4)  # A -> C, weight 4
g.add_edge(2, 0, -3) # C -> A, weight -3
g.add_edge(0, 4, 5)  # A -> E, weight 5
g.add_edge(4, 2, 3)  # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2)  # E -> B, weight 2

# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
negative_cycle, distances, predecessors = g.bellman_ford('D')
if not negative_cycle:
    for i, d in enumerate(distances):
        if d != float('inf'):
            path = g.get_path(predecessors, 'D', g.vertex_data[i])
            print(f"{path}, Distance: {d}")
        else:
            print(f"No path from D to {g.vertex_data[i]}, Distance: Infinity")
else:
    print("Negative weight cycle detected. Cannot compute shortest paths.")

19-qator: predecessors massivi eng qisqa yo‘lda har bir cho‘qqidan oldingi cho‘qqini saqlaydi.

28-qator: Har safar qirra relaksatsiya qilinganda predecessors massivi yangi oldingi cho‘qqi bilan yangilanadi.

40–49-qatorlar: get_path metodi har bir cho‘qqi uchun eng qisqa yo‘l stringini hosil qilishda predecessors massividan foydalanadi.

Bellman-Ford algoritmining vaqt murakkabligi

Bellman-Ford algoritmining vaqt murakkabligi asosan ichma-ich joylashgan sikllarga bog‘liq.

Tashqi for sikli \(V-1\) marta, manfiy sikllarni aniqlash ham bo‘lsa, \(V\) marta ishlaydi. Cho‘qqilari ko‘p graflarda barcha qirralarni cho‘qqilar sonidan bir marta kam tekshirish katta farq qilmaydi, shuning uchun tashqi sikl vaqt murakkabligiga \(O(V)\) hissa qo‘shadi, deyishimiz mumkin.

Ikkita ichki for sikli grafdagi barcha qirralarni tekshiradi. Vaqt murakkabligi nuqtayi nazaridan eng yomon holatni faraz qilsak, bizda har bir cho‘qqi boshqa har bir cho‘qqi bilan qirra orqali bog‘langan juda zich graf bo‘ladi, ya’ni barcha \(V\) cho‘qqilar uchun boshqa barcha \(V\) cho‘qqilarga boradigan qirrani tekshirish kerak; bu vaqt murakkabligiga \(O(V^2)\) hissa qo‘shadi.

Shunday qilib, jami Bellman-Ford algoritmi uchun quyidagi vaqt murakkabligini olamiz:

\[ O(V^3) \]

Biroq amaliy vaziyatlarda, ayniqsa siyrak graflarda, ya’ni har bir cho‘qqi boshqa cho‘qqilarning faqat kichik qismi bilan qirralar orqali bog‘langan bo‘lsa, barcha qirralarni tekshiruvchi ikkita ichki for siklining vaqt murakkabligini \(O(V^2)\) dan \(O(E)\) ga taqriban keltirish mumkin va Bellman-Ford uchun umumiy vaqt murakkabligini olamiz:

\[ O(V \cdot E) \]

Bellman-Ford algoritmining vaqt murakkabligi Dijkstra algoritminikiga qaraganda sekinroq, ammo Bellman-Ford manfiy qirrali graflarda eng qisqa yo‘llarni topa oladi va manfiy sikllarni aniqlay oladi — Dijkstra algoritmi buni qila olmaydi.

DSA mashqlari

Mashqlar yordamida o‘zingizni sinang

Mashq:

Quyidagi qo‘shnilik matritsasida:

D’dan E’ga boradigan qirraning vazni qancha?

The D->E edge weight is .

Javobni yuborish »

Mashqni boshlash