DSA Dijkstra algoritmi

Dijkstra algoritmi

Dijkstra algoritmi bitta cho‘qqidan boshqa barcha cho‘qqilargacha bo‘lgan eng qisqa yo‘lni topadi.

U buni hali tashrif buyurilmagan eng yaqin cho‘qqini qayta-qayta tanlab, barcha tashrif buyurilmagan qo‘shni cho‘qqilargacha bo‘lgan masofani hisoblash orqali amalga oshiradi.

Dijkstra algoritmi ko‘pincha eng qisqa yo‘l masalasini yechishning eng sodda algoritmi hisoblanadi.

Dijkstra algoritmi yo‘naltirilgan yoki yo‘naltirilmagan yo‘llar uchun yagona manbali eng qisqa yo‘l masalalarini yechishda qo‘llaniladi. "Yagona manbali" degani — boshlang‘ich nuqta sifatida bitta cho‘qqi tanlanadi va algoritm shu cho‘qqidan boshqa barcha cho‘qqilargacha eng qisqa yo‘lni topadi.

Dijkstra algoritmi manfiy qirrali graflar uchun ishlamaydi. Manfiy qirrali graflar uchun uning o‘rniga keyingi sahifada tasvirlangan Bellman-Ford algoritmidan foydalanish mumkin.

Eng qisqa yo‘lni topish uchun Dijkstra algoritmi qaysi cho‘qqi manba ekanini bilishi, cho‘qqilarni tashrif buyurilgan deb belgilash usuliga ega bo‘lishi hamda graf bo‘ylab ishlash davomida har bir cho‘qqigacha bo‘lgan joriy eng qisqa masofani kuzatib borishi va qisqaroq masofa topilganda bu masofalarni yangilab turishi kerak.

Yuqoridagi animatsiyada cho‘qqi tashrif buyurilgan deb belgilanganda, Dijkstra algoritmi bu cho‘qqi bilan ishni tugatgani va unga qayta tashrif buyurmasligini ko‘rsatish uchun cho‘qqi va uning qirralari xiralashadi.

Dijkstra algoritmining batafsil simulyatsiyasi

Dijkstra algoritmi muayyan grafda D cho‘qqisidan eng qisqa masofalarni qanday topishini batafsilroq tushunish uchun quyidagi simulyatsiyani ishga tushiring.

Bu simulyatsiya keyingi cho‘qqi sifatida har doim boshlang‘ich nuqtaga eng yaqin tashrif buyurilmagan cho‘qqini tanlash orqali D cho‘qqisidan boshqa barcha cho‘qqilargacha masofalar qanday hisoblanishini ko‘rsatadi.

Dijkstra algoritmi eng qisqa masofalarni qanday hisoblashining barcha tafsilotlarini bilish uchun quyidagi qadamma-qadam tavsifni kuzatib boring.

Qo‘lda bajarib ko‘rish

Quyidagi grafni ko‘rib chiqing.

Biz D manba cho‘qqisidan boshqa barcha cho‘qqilargacha eng qisqa yo‘lni topmoqchimiz; masalan, C’gacha eng qisqa yo‘l D->E->C bo‘lib, uning yo‘l vazni 2+4=6 ga teng.

Eng qisqa yo‘lni topish uchun Dijkstra algoritmi boshqa barcha cho‘qqilargacha bo‘lgan masofalarni saqlovchi massivdan foydalanadi va dastlab bu masofalarni cheksiz yoki juda katta songa tenglaydi. Ish boshlanadigan cho‘qqigacha (manbagacha) bo‘lgan masofa esa 0 ga tenglanadi.

distances = [inf, inf, inf, 0, inf, inf, inf]
#vertices   [ A ,  B ,  C , D,  E ,  F ,  G ]

Quyidagi rasmda boshlang‘ich D cho‘qqisidan boshqa cho‘qqilargacha bo‘lgan dastlabki cheksiz masofalar ko‘rsatilgan. D cho‘qqisi uchun masofa qiymati 0, chunki u boshlang‘ich nuqta.

Keyin Dijkstra algoritmi D cho‘qqisini joriy cho‘qqi qilib belgilaydi va qo‘shni cho‘qqilargacha bo‘lgan masofaga qaraydi. A va E cho‘qqilarigacha dastlabki masofa cheksiz bo‘lgani uchun ularga yangi masofa sifatida qirra vaznlari yoziladi. Shunday qilib, A cho‘qqisining masofasi inf dan 4 ga, E cho‘qqisiniki esa 2 ga o‘zgaradi. Oldingi sahifada aytib o‘tilganidek, masofa qiymatlarini shu tarzda yangilash "relaksatsiya" (relaxing) deb ataladi.

A va E cho‘qqilari relaksatsiya qilingach, D cho‘qqisi tashrif buyurilgan hisoblanadi va unga qayta tashrif buyurilmaydi.

Keyingi joriy cho‘qqi sifatida avval tashrif buyurilmagan cho‘qqilar orasidan manba cho‘qqigacha (D cho‘qqisigacha) eng qisqa masofaga ega cho‘qqi tanlanishi kerak. Shu sababli D cho‘qqisidan keyin joriy cho‘qqi sifatida E cho‘qqisi tanlanadi.

Endi E cho‘qqisidan unga qo‘shni va avval tashrif buyurilmagan barcha cho‘qqilargacha bo‘lgan masofa hisoblanishi va kerak bo‘lsa yangilanishi lozim.

D’dan E orqali A cho‘qqisigacha hisoblangan masofa 2+4=6 ga teng. Ammo A cho‘qqisigacha joriy masofa allaqachon 4 — bu kichikroq, shuning uchun A cho‘qqisigacha masofa yangilanmaydi.

C cho‘qqisigacha masofa 2+4=6 deb hisoblanadi, bu cheksizlikdan kichik, shuning uchun C cho‘qqisigacha masofa yangilanadi.

Xuddi shunday, G tugunigacha masofa hisoblanadi va 2+5=7 ga yangilanadi.

Keyingi tashrif buyuriladigan cho‘qqi — A, chunki barcha tashrif buyurilmagan cho‘qqilar orasida D’dan eng qisqa masofa unga tegishli.

A orqali C cho‘qqisigacha hisoblangan masofa 4+3=7 ga teng, bu C cho‘qqisi uchun allaqachon belgilangan masofadan katta, shuning uchun C cho‘qqisigacha masofa yangilanmaydi.

Endi A cho‘qqisi tashrif buyurilgan deb belgilanadi, keyingi joriy cho‘qqi esa C bo‘ladi, chunki qolgan tashrif buyurilmagan cho‘qqilar orasida D cho‘qqisidan eng kichik masofa unga tegishli.

F cho‘qqisining masofasi 6+5=11 ga, B cho‘qqisiniki esa 6+2=8 ga yangilanadi.

C cho‘qqisi orqali G cho‘qqisigacha hisoblangan masofa 6+5=11 ga teng, bu allaqachon belgilangan 7 masofadan katta, shuning uchun G cho‘qqisigacha masofa yangilanmaydi.

C cho‘qqisi tashrif buyurilgan deb belgilanadi, keyingi tashrif buyuriladigan cho‘qqi esa G, chunki qolgan tashrif buyurilmagan cho‘qqilar orasida eng kichik masofa unga tegishli.

F cho‘qqisining masofasi allaqachon 11 ga teng. Bu G orqali hisoblangan 7+5=12 masofadan kichik, shuning uchun F cho‘qqisigacha masofa yangilanmaydi.

G cho‘qqisi tashrif buyurilgan deb belgilanadi va B joriy cho‘qqiga aylanadi, chunki qolgan tashrif buyurilmagan cho‘qqilar orasida eng kichik masofa unga tegishli.

B orqali F’gacha yangi masofa 8+2=10 bo‘ladi, chunki u F’ning mavjud 11 masofasidan kichik.

B cho‘qqisi tashrif buyurilgan deb belgilanadi, oxirgi tashrif buyurilmagan F cho‘qqisi uchun esa tekshiradigan hech narsa yo‘q, shuning uchun Dijkstra algoritmi o‘z ishini tugatadi.

Har bir cho‘qqiga faqat bir marta tashrif buyurildi va natijada D manba cho‘qqisidan grafdagi boshqa har bir cho‘qqigacha bo‘lgan eng kichik masofa olindi.

Dijkstra algoritmini amalga oshirish

Dijkstra algoritmini amalga oshirish uchun Graph sinfini yaratamiz. Graph grafni uning cho‘qqilari va qirralari bilan birga ifodalaydi:

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

3-qator: Barcha qirralar va qirra vaznlarini saqlash uchun adj_matrixni yaratamiz. Boshlang‘ich qiymatlar 0ga tenglanadi.

4-qator: size — grafdagi cho‘qqilar soni.

5-qator: vertex_data barcha cho‘qqilarning nomlarini saqlaydi.

7–10-qatorlar: add_edge metodi u cho‘qqisidan v cho‘qqisiga weight vaznli qirra qo‘shish uchun ishlatiladi.

12–14-qatorlar: add_vertex_data metodi grafga cho‘qqi qo‘shish uchun ishlatiladi. Cho‘qqi joylashishi kerak bo‘lgan indeks vertex argumenti orqali beriladi, data esa cho‘qqining nomi.

Graph sinfi Dijkstra algoritmini ishga tushiradigan metodni ham o‘z ichiga oladi:

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

        for _ in range(self.size):
            min_distance = float('inf')
            u = None
            for i in range(self.size):
                if not visited[i] and distances[i] < min_distance:
                    min_distance = distances[i]
                    u = i

            if u is None:
                break

            visited[u] = True

            for v in range(self.size):
                if self.adj_matrix[u][v] != 0 and not visited[v]:
                    alt = distances[u] + self.adj_matrix[u][v]
                    if alt < distances[v]:
                        distances[v] = alt

        return distances

18–19-qatorlar: distances massivida boshlang‘ich cho‘qqidan tashqari barcha cho‘qqilar uchun dastlabki masofa cheksizlikka tenglanadi, boshlang‘ich cho‘qqi uchun esa masofa 0 ga teng.

20-qator: visited massivida barcha cho‘qqilar tashrif buyurilmagan deb belgilanishi uchun dastlab Falsega tenglanadi.

23–28-qatorlar: Keyingi joriy cho‘qqi topiladi. Qisqaroq masofalar topish mumkinligini aniqlash uchun bu cho‘qqidan chiquvchi qirralar tekshiriladi. U boshlang‘ich nuqtadan eng kichik masofadagi tashrif buyurilmagan cho‘qqidir.

30–31-qatorlar: Agar keyingi joriy cho‘qqi topilmasa, algoritm tugaydi. Bu manbadan yetib borish mumkin bo‘lgan barcha cho‘qqilarga tashrif buyurilganini bildiradi.

33-qator: Qo‘shni cho‘qqilarni relaksatsiya qilishdan oldin joriy cho‘qqi tashrif buyurilgan deb belgilanadi. Bu samaraliroq, chunki shunda joriy cho‘qqining o‘zigacha bo‘lgan masofani tekshirishdan qochamiz.

35–39-qatorlar: Tashrif buyurilmagan qo‘shni cho‘qqilar uchun masofalar hisoblanadi va yangi hisoblangan masofa kichikroq bo‘lsa, yangilanadi.

Graph sinfini aniqlagach, muayyan grafni initsializatsiya qilish uchun cho‘qqilar va qirralarni aniqlash kerak. Dijkstra algoritmi bo‘yicha ushbu misolning to‘liq kodi 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 dijkstra(self, start_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        distances = [float('inf')] * self.size
        distances[start_vertex] = 0
        visited = [False] * self.size

        for _ in range(self.size):
            min_distance = float('inf')
            u = None
            for i in range(self.size):
                if not visited[i] and distances[i] < min_distance:
                    min_distance = distances[i]
                    u = i

            if u is None:
                break

            visited[u] = True

            for v in range(self.size):
                if self.adj_matrix[u][v] != 0 and not visited[v]:
                    alt = distances[u] + self.adj_matrix[u][v]
                    if alt < distances[v]:
                        distances[v] = alt

        return distances

g = Graph(7)

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_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

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

# Dijkstra's algorithm from D to all vertices
print("\nDijkstra's Algorithm starting from vertex D:")
distances = g.dijkstra('D')
for i, d in enumerate(distances):
    print(f"Distance from D to {g.vertex_data[i]}: {d}")

Yo‘naltirilgan graflarda Dijkstra algoritmi

Dijkstra algoritmini yo‘naltirilgan graflarda ishlatish uchun juda kam o‘zgartirish talab etiladi.

Yo‘naltirilgan graflarda sikllarni aniqlash uchun kiritgan o‘zgarishimiz singari, qo‘shnilik matritsasi endi simmetrik bo‘lmasligi uchun faqat bitta kod qatorini olib tashlashimiz kifoya.

Keling, ushbu yo‘naltirilgan grafni amalga oshiramiz va Dijkstra algoritmini D cho‘qqisidan ishga tushiramiz.

Mana, D manba cho‘qqisi bo‘lgan yo‘naltirilgan grafda Dijkstra algoritmining amalga oshirilishi:

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 dijkstra(self, start_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        distances = [float('inf')] * self.size
        distances[start_vertex] = 0
        visited = [False] * self.size

        for _ in range(self.size):
            min_distance = float('inf')
            u = None
            for i in range(self.size):
                if not visited[i] and distances[i] < min_distance:
                    min_distance = distances[i]
                    u = i

            if u is None:
                break

            visited[u] = True

            for v in range(self.size):
                if self.adj_matrix[u][v] != 0 and not visited[v]:
                    alt = distances[u] + self.adj_matrix[u][v]
                    if alt < distances[v]:
                        distances[v] = alt

        return distances

g = Graph(7)

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_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

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

# Dijkstra's algorithm from D to all vertices
print("Dijkstra's Algorithm starting from vertex D:\n")
distances = g.dijkstra('D')
for i, d in enumerate(distances):
    print(f"Shortest distance from D to {g.vertex_data[i]}: {d}")

Quyidagi rasmda Dijkstra algoritmi hisoblagan D cho‘qqisidan eng qisqa masofalar ko‘rsatilgan.

Bu natija yo‘naltirilmagan grafda Dijkstra algoritmidan foydalanilgan oldingi misolga o‘xshaydi. Biroq asosiy farq bor: bu holda D’dan B cho‘qqisiga borib bo‘lmaydi, demak D’dan F’gacha eng qisqa masofa endi 10 emas, balki 11, chunki yo‘l endi B cho‘qqisi orqali o‘ta olmaydi.

Dijkstra algoritmidan yo‘llarni qaytarish

Bir nechta o‘zgartirish kiritilsa, Dijkstra algoritmi eng qisqa yo‘l qiymatlaridan tashqari eng qisqa yo‘llarning o‘zini ham qaytarishi mumkin. Masalan, algoritm D cho‘qqisidan F’gacha eng qisqa yo‘l qiymati 10 ekanini qaytarish bilan cheklanmay, eng qisqa yo‘l "D->E->C->B->F" ekanini ham qaytarishi mumkin.

Yo‘lni qaytarish uchun har bir cho‘qqi uchun eng qisqa yo‘ldagi oldingi cho‘qqini saqlaydigan predecessors massivini yaratamiz. predecessors massivi yordamida orqaga qaytib, har bir cho‘qqi uchun eng qisqa yo‘lni topish mumkin.

class Graph:
    # ... (rest of the Graph class)

    def dijkstra(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
        visited = [False] * self.size

        for _ in range(self.size):
            min_distance = float('inf')
            u = None
            for i in range(self.size):
                if not visited[i] and distances[i] < min_distance:
                    min_distance = distances[i]
                    u = i

            if u is None:
                break

            visited[u] = True

            for v in range(self.size):
                if self.adj_matrix[u][v] != 0 and not visited[v]:
                    alt = distances[u] + self.adj_matrix[u][v]
                    if alt < distances[v]:
                        distances[v] = alt
                        predecessors[v] = u

        return distances, predecessors

    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)  # Join the vertices with '->'

g = Graph(7)

# ... (rest of the graph setup)

# Dijkstra's algorithm from D to all vertices
print("Dijkstra's Algorithm starting from vertex D:\n")
distances, predecessors = g.dijkstra('D')
for i, d in enumerate(distances):
    path = g.get_path(predecessors, 'D', g.vertex_data[i])
    print(f"{path}, Distance: {d}")

7- va 29-qatorlar: predecessors massivi avval None qiymatlari bilan initsializatsiya qilinadi, so‘ngra eng qisqa yo‘l qiymatlari yangilangani sari har bir cho‘qqi uchun to‘g‘ri oldingi cho‘qqi (predecessor) bilan yangilanadi.

33–42-qatorlar: get_path metodi predecessors massividan foydalanadi va boshlang‘ich cho‘qqidan oxirgi cho‘qqigacha eng qisqa yo‘lni ifodalovchi stringni qaytaradi.

Yagona manzil cho‘qqili Dijkstra algoritmi

Aytaylik, bizni faqat ikki cho‘qqi orasidagi eng qisqa yo‘lni topish qiziqtiradi, masalan, quyidagi grafda D cho‘qqisi va F cho‘qqisi orasidagi eng qisqa masofani topish.

Dijkstra algoritmi odatda bitta manba cho‘qqidan grafdagi boshqa barcha cho‘qqilargacha eng qisqa yo‘lni topish uchun ishlatiladi, lekin uni manbadan faqat bitta manzil cho‘qqigacha eng qisqa yo‘lni topadigan qilib ham o‘zgartirish mumkin — buning uchun manzilga yetib borilganda (unga tashrif buyurilganda) algoritmni to‘xtatish kifoya.

Bu shuni anglatadiki, yuqoridagi rasmdagi muayyan graf uchun Dijkstra algoritmi F’ga (manzil cho‘qqiga) tashrif buyurgach, H, I va J cho‘qqilariga tashrif buyurishdan oldin to‘xtaydi, chunki ular D’dan F’ga qaraganda uzoqroqda joylashgan.

Quyida Dijkstra algoritmi D’dan F’gacha eng qisqa masofani topib, ishini to‘xtatgan paytdagi hisoblangan masofalar holatini ko‘rishimiz mumkin.

Yuqoridagi rasmda F cho‘qqisi hozirgina B cho‘qqisi orqali 10 masofa bilan yangilandi. F cho‘qqisi D’dan eng kichik masofadagi tashrif buyurilmagan cho‘qqi bo‘lgani uchun odatda u keyingi joriy cho‘qqi bo‘lardi, ammo u manzil bo‘lgani sababli algoritm to‘xtaydi. Agar algoritm to‘xtamaganida, masofasi yangilanadigan keyingi cho‘qqi J bo‘lardi: I cho‘qqisi orqali 11+2=13.

Quyidagi kod yagona manzil cho‘qqigacha eng qisqa yo‘lni topish uchun amalga oshirilgan Dijkstra algoritmidir:

class Graph:
    # ... (existing methods)

    def dijkstra(self, start_vertex_data, end_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        end_vertex = self.vertex_data.index(end_vertex_data)
        distances = [float('inf')] * self.size
        predecessors = [None] * self.size
        distances[start_vertex] = 0
        visited = [False] * self.size

        for _ in range(self.size):
            min_distance = float('inf')
            u = None
            for i in range(self.size):
                if not visited[i] and distances[i] < min_distance:
                    min_distance = distances[i]
                    u = i

            if u is None or u == end_vertex:
                print(f"Breaking out of loop. Current vertex: {self.vertex_data[u]}")
                print(f"Distances: {distances}")
                break

            visited[u] = True
            print(f"Visited vertex: {self.vertex_data[u]}")

            for v in range(self.size):
                if self.adj_matrix[u][v] != 0 and not visited[v]:
                    alt = distances[u] + self.adj_matrix[u][v]
                    if alt < distances[v]:
                        distances[v] = alt
                        predecessors[v] = u

        return distances[end_vertex], self.get_path(predecessors, start_vertex_data, end_vertex_data)

# Example usage
g = Graph(7)
# ... (rest of the graph setup)
distance, path = g.dijkstra('D', 'F')
print(f"Path: {path}, Distance: {distance}")

20–23-qatorlar: Agar manzil cho‘qqini joriy cho‘qqi sifatida tanlab, uni tashrif buyurilgan deb belgilamoqchi bo‘lsak, demak manzil cho‘qqigacha eng qisqa masofani allaqachon hisoblab bo‘lganmiz va yagona manzilli bu holatda Dijkstra algoritmini to‘xtatish mumkin.

Dijkstra algoritmining vaqt murakkabligi

Grafimizdagi cho‘qqilar soni \(V\) bo‘lsa, Dijkstra algoritmining vaqt murakkabligi quyidagiga teng

\[ O( V^2 ) \]

Bunday vaqt murakkabligi hosil bo‘lishining sababi shundaki, keyingi joriy cho‘qqini tanlash uchun eng kichik masofali cho‘qqini qidirish kerak va bu \(O(V)\) vaqt oladi. Bu ish manbaga bog‘langan har bir cho‘qqi uchun bajarilishi kerakligi sababli buni ham hisobga olishimiz lozim va natijada Dijkstra algoritmi uchun \(O(V^2)\) vaqt murakkabligini olamiz.

Buning o‘rniga masofalar uchun Min-heap yoki Fibonacci-heap ma’lumotlar tuzilmasidan foydalanilsa (ular bu darslikda hali tushuntirilmagan), eng kichik masofali cho‘qqini qidirish uchun ketadigan vaqt \(O(V)\) dan \(O( \log{V})\) gacha kamayadi va natijada Dijkstra algoritmining vaqt murakkabligi quyidagicha yaxshilanadi

\[ O( V \cdot \log{V} + E ) \]

Bu yerda \(V\) — grafdagi cho‘qqilar soni, \(E\) esa qirralar soni.

Dijkstra algoritmi uchun Min-heap ma’lumotlar tuzilmasidan foydalanish beradigan yaxshilanish, ayniqsa, katta va siyrak graflarda sezilarli bo‘ladi; siyrak graf deganda cho‘qqilari ko‘p, ammo qirralari unchalik ko‘p bo‘lmagan graf tushuniladi.

Dijkstra algoritmini Fibonacci-heap ma’lumotlar tuzilmasi bilan amalga oshirish zich graflar uchun yaxshiroq; zich grafda har bir cho‘qqi deyarli boshqa barcha cho‘qqilar bilan qirra orqali bog‘langan bo‘ladi.

DSA mashqlari

Mashqlar yordamida o‘zingizni sinang

Mashq:

Ushbu grafda C cho‘qqisidan eng qisqa yo‘llarni topish uchun Dijkstra algoritmidan foydalanilganda:

C’ga tashrif buyurilgandan keyin navbatdagi tashrif buyuriladigan cho‘qqi qaysi?

Using Dijkstra's algorithm,
the next vertex to be visited 
after vertex C is vertex .

Javobni yuborish »

Mashqni boshlash