Floyd-Warshall Algorithm

Floyd-Warshall algoritmi — bu musbat yoki manfiy og'irlikdagi qirralarga ega yo'naltirilgan grafda barcha cho'qqilar juftliklari orasidagi eng qisqa yo'llarni (all-pairs shortest paths) topuvchi algoritmdir. Biroq, grafda manfiy vaznli sikllar (negative cycles) bo'lmasligi lozim.

U bitta boshlang'ich manbadan qidiruvchi Dijkstra algoritmidan farqli o'laroq, grafdagi har qanday ikki cho'qqi (i, j) orasidagi masofani bir vaqtning o'zida hisoblaydi va dinamik dasturlash tamoyillariga tayanadi.

Floyd-Warshall algoritmi qanday ishlaydi?

Faraz qilaylik, bizga quyidagi yo'naltirilgan vaznli graf berilgan:

Boshlang'ich graf (Initial Graph)

Barcha cho'qqilar juftliklari orasidagi eng qisqa masofani topish uchun quyidagi qadamlar bajariladi:

1. O'lchami n * n bo'lgan A⁰ matritsasini yaratamiz (n — cho'qqilar soni). Qatorlar i va ustunlar j mos ravishda grafning cho'qqilarini bildiradi.

   Har bir katak A[i][j] ga i-cho'qqidan j-cho'qqigacha bo'lgan qirra og'irligi yoziladi. Agar i va j orasida to'g'ridan-to'g'ri qirra mavjud bo'lmasa, u holda cheksizlik (∞) qiymati qo'yiladi. O'zidan o'ziga boruvchi yo'llar esa 0 ga teng.

   

   Dastlabki masofalar matritsasi A⁰ (Matrix A⁰)

2. Endi A⁰ matritsasidan foydalanib A¹ matritsasini tuzamiz. Birinchi qator va birinchi ustun elementlari o'zgarishsiz qoldiriladi. Qolgan barcha kataklar quyidagi qoida bo'yicha to'ldiriladi:

   Faraz qilaylik, k — manbadan manzilgacha bo'lgan eng qisqa yo'ldagi oraliq cho'qqi. Ushbu qadamda k sifatida 1-cho'qqi olinadi. Agar A[i][j] > A[i][k] + A[k][j] bo'lsa, A[i][j] katagiga A[i][k] + A[k][j] qiymati yoziladi.

   Ya'ni, manbadan manzilga to'g'ridan-to'g'ri borish masofasi 1-cho'qqi orqali o'tish masofasidan katta bo'lsa, qisqaroq yangi masofa tanlanadi.

   

   1-cho'qqi (k = 1) orqali hisoblangan masofalar (Matrix A¹)

   Masalan: A¹[2, 4] uchun 2-cho'qqidan 4-cho'qqiga to'g'ridan-to'g'ri masofa 4 ga teng, 1-cho'qqi orqali o'tish esa 2 -> 1 (2) + 1 -> 4 (5) = 7 ga teng. 4 < 7 bo'lgani sababli A¹[2, 4] da 4 saqlanib qoladi.

3. Xuddi shunday tarzda, A¹ dan foydalanib A² matritsasi quriladi. Bunda ikkinchi qator va ikkinchi ustun elementlari o'zgarishsiz qoladi va oraliq cho'qqi sifatida 2-cho'qqi (k = 2) tekshiriladi:

   

   2-cho'qqi (k = 2) orqali hisoblangan masofalar (Matrix A²)

4. Shu tariqa navbatdagi cho'qqilar uchun A³ va A⁴ matritsalari ham bosqichma-bosqich hisoblanadi:

   

   3-cho'qqi (k = 3) orqali hisoblangan masofalar (Matrix A³)

   

   4-cho'qqi (k = 4) orqali hisoblangan yakuniy masofalar (Matrix A⁴)

5. Oxirgi hosil bo'lgan A⁴ matritsasi grafdagi barcha cho'qqilar juftligi orasidagi eng qisqa masofalarni taqdim etadi.

Floyd-Warshall algoritmi psevdokodi

n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
    for i = 1 to n
        for j = 1 to n
            A[i, j] = min (A[i, j], A[i, k] + A[k, j])
return A

Dasturiy kod

package main

import (
	"fmt"
)

const INF = 999
const nV = 4

// Floyd-Warshall algoritmini amalga oshirish
func floydWarshall(G [][]int) {
	matrix := make([][]int, nV)
	for i := 0; i < nV; i++ {
		matrix[i] = make([]int, nV)
		copy(matrix[i], G[i])
	}

	// Har bir cho'qqini oraliq tugun sifatida alohida qo'shib chiqish
	for k := 0; k < nV; k++ {
		for i := 0; i < nV; i++ {
			for j := 0; j < nV; j++ {
				if matrix[i][k]+matrix[k][j] < matrix[i][j] {
					matrix[i][j] = matrix[i][k] + matrix[k][j]
				}
			}
		}
	}

	printSolution(matrix)
}

// Natijaviy matritsani chop etish
func printSolution(matrix [][]int) {
	for i := 0; i < nV; i++ {
		for j := 0; j < nV; j++ {
			if matrix[i][j] == INF {
				fmt.Print("INF ")
			} else {
				fmt.Printf("%3d ", matrix[i][j])
			}
		}
		fmt.Println()
	}
}

func main() {
	G := [][]int{
		{0, 3, INF, 5},
		{2, 0, INF, 4},
		{INF, 1, 0, INF},
		{INF, INF, 2, 0},
	}

	floydWarshall(G)
}

Floyd-Warshall algoritmining murakkabligi

Vaqt murakkabligi

Algoritmda bir-birining ichiga joylashgan 3 ta sikl (loop) mavjud bo'lib, har biri n marta aylanadi. Shuning uchun Floyd-Warshall algoritmining vaqt murakkabligi: O(n^3) (bu yerda n — grafdagi cho'qqilar soni).

Xotira murakkabligi

Masofalar matritsasini saqlash uchun O(n^2) hajmdagi xotira talab etiladi.

Floyd-Warshall algoritmining qo'llanilishi

• Yo'naltirilgan grafda eng qisqa yo'lni topish: Tarmoqdagi ixtiyoriy ikki uzel orasidagi marshrutni oldindan hisoblab qo'yish.
• Tranzitiv yopiqni (Transitive Closure) topish: Graflarda ixtiyoriy ikki cho'qqi orasida yo'l mavjud yoki yo'qligini aniqlash (Warshall algoritmi).
• Haqiqiy matritsalarning inversiyasini hisoblash.
• Yo'naltirilmagan grafning ikki qismli (bipartite) ekanligini tekshirish.