61 / 69

Dijkstra's Algorithm

Dijkstra algoritmi nima?

Dijkstra algoritmi — bu yo'naltirilgan yoki yo'naltirilmagan vaznli grafda bitta boshlang'ich cho'qqidan (manbadan) boshqa barcha cho'qqilarga olib boruvchi eng qisqa yo'lni topish algoritmidir.

U minimal qamrovchi daraxt (MST) algoritmidan farq qiladi, chunki ikki cho'qqi orasidagi eng qisqa masofa grafning barcha cho'qqilarini qamrab olishi shart emas.

Dijkstra algoritmi qanday ishlaydi?

Dijkstra algoritmi quyidagi qoidaga tayanadi: A va D cho'qqilari orasidagi eng qisqa yo'lning har qanday qism-yo'li B -> D ham o'z navbatida B va D cho'qqilari orasidagi eng qisqa yo'l hisoblanadi.

Har bir qism-yo'l ham eng qisqa yo'ldir

Har bir qism-yo'l ham eng qisqa yo'ldir (Shortest subpath property)

Dijkstra bu xususiyatdan teskari yo'nalishda foydalangan: dastlab boshlang'ich cho'qqidan boshqa barcha cho'qqilargacha bo'lgan masofani cheksiz katta (∞) deb taxmin qilamiz. So'ngra har bir tugun va uning qo'shnilariga tashrif buyurib, ushbu qo'shnilarga olib boruvchi eng qisqa qism-yo'lni bosqichma-bosqich aniqlab, masofani qisqartirib (bo'shashtirib / relax qilib) boramiz.

Algoritm greedy (ochko'z) yondashuvdan foydalanadi: har bir qadamda navbatdagi eng yaqin bo'lgan cho'qqini tanlab boradi va bu yakunda butun masala uchun eng maqbul yechimni berishini kafolatlaydi.

Dijkstra algoritmi misoli

Keling, algoritmni tushunish uchun vaznli graf misolini bosqichma-bosqich ko'rib chiqamiz.

Boshlang'ich vaznli graf berilgan:

Vaznli graf bilan boshlaymiz
Boshlang'ich cho'qqini tanlaymiz (masofa = 0) va boshqa barcha cho'qqilarga cheksiz (∞) masofa qiymatini o'rnatamiz:

Boshlang'ich cho'qqini tanlash va qolganlarga cheksizlik belgilash
Boshlang'ich cho'qqining har bir qo'shnisiga o'tib, ularning masofalarini yangilaymiz:

Qo'shni cho'qqilar masofasini yangilash
Agar qo'shni cho'qqining joriy masofasi yangi hisoblangan yo'ldan kichik bo'lsa, uni yangilamaymiz:

Agar qo'shni cho'qqining masofasi yangi yo'ldan kichik bo'lsa, uni yangilamaymiz
Allaqachon tashrif buyurilgan (yakuniy optimal masofasi aniqlangan) cho'qqilarning masofasini qayta yangilashdan saqlanamiz:

Allaqachon tashrif buyurilgan cho'qqilar masofasini qayta yangilamaslik
Har bir iteratsiyadan so'ng, tashrif buyurilmagan cho'qqilar orasidan eng kichik masofaga ega bo'lganini tanlaymiz (masalan, 7 dan oldin 5 tanlanadi):

Eng kichik masofali cho'qqini tanlash
E'tibor bering, eng o'ngdagi cho'qqining masofasi qisqaroq yangi yo'l topilishi hisobiga ikki marta yangilanadi:

Eng o'ngdagi cho'qqi masofasining ikki marta yangilanishi
Barcha cho'qqilarga tashrif buyurilguniga qadar jarayonni davom ettiramiz:

Barcha cho'qqilarga tashrif buyurilguncha takrorlash

Dijkstra algoritmi psevdokodi

Biz har bir cho'qqigacha bo'lgan yo'l masofasini saqlashimiz kerak. Buni V o'lchamli massivda saqlash mumkin (V — cho'qqilar soni).

Shuningdek, nafaqat eng qisqa yo'l uzunligini bilish, balki eng qisqa yo'lning o'zini (marshrutni) ham tiklay olishimiz kerak. Buning uchun har bir cho'qqiga uning masofasini oxirgi marta yangilagan o'tmishdosh (previous) cho'qqini bog'lab boramiz.

Algoritm tugagach, manzil cho'qqisidan boshlang'ich manbagacha orqaga qarab yo'lni (backtrack qilib) osongina tiklash mumkin.

Eng kichik masofaga ega cho'qqini tezkor olish uchun ustuvorlik navbati (priority queue / min-heap) qo'llaniladi.

text

function dijkstra(G, S)
    for each vertex V in G
        distance[V] <- infinite
        previous[V] <- NULL
        If V != S, add V to Priority Queue Q
    distance[S] <- 0
	
    while Q IS NOT EMPTY
        U <- Extract MIN from Q
        for each unvisited neighbour V of U
            tempDistance <- distance[U] + edge_weight(U, V)
            if tempDistance < distance[V]
                distance[V] <- tempDistance
                previous[V] <- U
    return distance[], previous[]

Dasturiy kod

package main

import (
	"fmt"
	"math"
)

func main() {
	vertices := [][]int{
		{0, 0, 1, 1, 0, 0, 0},
		{0, 0, 1, 0, 0, 1, 0},
		{1, 1, 0, 1, 1, 0, 0},
		{1, 0, 1, 0, 0, 0, 1},
		{0, 0, 1, 0, 0, 1, 0},
		{0, 1, 0, 0, 1, 0, 1},
		{0, 0, 0, 1, 0, 1, 0},
	}

	edges := [][]int{
		{0, 0, 1, 2, 0, 0, 0},
		{0, 0, 2, 0, 0, 3, 0},
		{1, 2, 0, 1, 3, 0, 0},
		{2, 0, 1, 0, 0, 0, 1},
		{0, 0, 3, 0, 0, 2, 0},
		{0, 3, 0, 0, 2, 0, 1},
		{0, 0, 0, 1, 0, 1, 0},
	}

	n := len(vertices)
	visited := make([]bool, n)
	distance := make([]int, n)

	for i := 0; i < n; i++ {
		distance[i] = math.MaxInt32
	}
	distance[0] = 0

	for count := 0; count < n; count++ {
		// Tashrif buyurilmagan va masofasi minimal bo'lgan cho'qqini topish
		minDist := math.MaxInt32
		u := -1
		for i := 0; i < n; i++ {
			if !visited[i] && distance[i] <= minDist {
				minDist = distance[i]
				u = i
			}
		}

		if u == -1 {
			break
		}

		visited[u] = true

		for v := 0; v < n; v++ {
			if vertices[u][v] == 1 && !visited[v] {
				newDist := distance[u] + edges[u][v]
				if newDist < distance[v] {
					distance[v] = newDist
				}
			}
		}
	}

	// Masofalarni chop etish
	for i := 0; i < n; i++ {
		fmt.Printf("Distance of %c from source vertex: %d\n", 'a'+i, distance[i])
	}
}

Dijkstra algoritmining murakkabligi

Vaqt murakkabligi (Time Complexity): O(E log V), bu yerda E — qirralar soni, V — cho'qqilar soni (min-heap / priority queue yordamida amalga oshirilganda). Oddiy massiv yordamida amalga oshirilganda esa O(V^2) bo'ladi.
Xotira murakkabligi (Space Complexity): O(V).

Dijkstra algoritmining qo'llanilishi

Eng qisqa yo'lni topish: GPS navigatsiya tizimlari va xaritalarda eng maqbul yo'nalishlarni hisoblash.
Ijtimoiy tarmoq ilovalari: Foydalanuvchilar orasidagi bog'liqlik darajalarini va do'stlik masofalarini aniqlash.
Telefon va aloqa tarmoqlari: Ma'lumot paketlarini eng kam kechikishli kanallar orqali uzatish.

Oldingi

Keyingi