{\ displaystyle \ Theta

Floyd-Warshall algoritmi har bir vertikal juftlik orasidagi grafik orqali mumkin bo'lgan barcha yo'llarni taqqoslaydi. Bu bilan buni amalga oshirishga qodir{\ displaystyle \ Theta (| V | ^ {3})} Grafikdagi taqqoslashlar, garchi ular bo'lishi mumkin bo'lsa ham {\ displaystyle \ Omega (| V | ^ {2})}grafikdagi qirralar va har bir qirralarning kombinatsiyasi sinovdan o'tkaziladi. Buni ikki vertikal orasidagi eng qisqa yo'ldagi smeta asta-sekin yaxshilanib, smeta optimal bo'lgunga qadar amalga oshiradi.

Grafikni ko'rib chiqaylik {\ displaystyle G} uchlari bilan {\ displaystyle V} 1 orqali raqamlangan {\ displaystyle N}. Keyinchalik funktsiyani ko'rib chiqing{\ displaystyle \ mathrm {shortestPath} (i, j, k)} dan eng qisqa yo'lni qaytaradi {\ displaystyle i} ga {\ displaystyle j} faqat to'plamdan vertikalarni ishlatish {\ displaystyle \ {1,2, \ ldots, k \}}yo'l bo'ylab oraliq nuqtalar sifatida. Endi ushbu funktsiyani hisobga olgan holda, bizning maqsadimiz har biridan eng qisqa yo'lni topishdir{\ displaystyle i} har biriga {\ displaystyle j}ichidagi har qanday balandlikdan foydalanish{\ displaystyle \ {1,2, \ ldots, N \}}.

Ushbu juft vertikallarning har biri uchun {\ displaystyle \ mathrm {shortestPath} (i, j, k)} ham bo'lishi mumkin

(1) o'tmaydigan yo'l {\ displaystyle k} (faqat to'plamdagi vertikallardan foydalanadi) {\ displaystyle \ {1, \ ldots, k-1 \}}.)

yoki

(2) o'tadigan yo'l {\ displaystyle k} (dan {\ displaystyle i} ga {\ displaystyle k} va keyin {\ displaystyle k} ga {\ displaystyle j}, ikkalasi ham faqat oraliq vertikallardan foydalangan holda {\ displaystyle \ {1, \ ldots, k-1 \}})

Biz bilamizki, bu eng yaxshi yo'l {\ displaystyle i} ga {\ displaystyle j} faqat vertikallardan foydalanadi {\ displaystyle 1} orqali {\ displaystyle k-1} tomonidan belgilanadi {\ displaystyle \ mathrm {shortestPath} (i, j, k-1)}, va agar yaxshiroq yo'l bo'lsa edi aniq {\ displaystyle i} ga {\ displaystyle k} ga {\ displaystyle j}, bu yo'lning uzunligi eng qisqa yo'lning o'zaro bog'lanishidir {\ displaystyle i} ga {\ displaystyle k} (faqat ichidagi oraliq vertikallardan foydalanib) {\ displaystyle \ {1, \ ldots, k-1 \}}) va eng qisqa yo'l {\ displaystyle k} ga {\ displaystyle j} (faqat ichidagi oraliq vertikallardan foydalanib) {\ displaystyle \ {1, \ ldots, k-1 \}}).

Agar {\ displaystyle w (i, j)} vertikallar orasidagi chekkaning og'irligi {\ displaystyle i} va {\ displaystyle j}, biz aniqlay olamiz {\ displaystyle \ mathrm {shortestPath} (i, j, k)}quyidagi rekursiv formuladan kelib chiqqan holda: asosiy holat

{\ displaystyle \ mathrm {shortestPath} (i, j, 0) = w (i, j)}

va rekursiv holat bu

{\ displaystyle \ mathrm {shortestPath} (i, j, k) =}

{\ displaystyle \ mathrm {min} {\ Big (} \ mathrm {shortestPath} (i, j, k-1),}

{\ displaystyle \ mathrm {shortestPath} (i, k, k-1) + \ mathrm {shortestPath} (k, j, k-1) {\ Katta)}}.

Ushbu formula Floyd-Warshall algoritmining yuragi. Algoritm birinchi hisoblash orqali ishlaydi{\ displaystyle \ mathrm {shortestPath} (i, j, k)} Barcha uchun {\ displaystyle (i, j)} uchun juftliklar {\ displaystyle k = 1}, keyin {\ displaystyle k = 2}, va hokazo. Bu jarayon qadar davom etadi{\ displaystyle k = N}, va biz hamma uchun eng qisqa yo'lni topdik {\ displaystyle (i, j)}har qanday oraliq vertikallardan foydalangan holda juftliklar. Ushbu asosiy versiya uchun psevdokod quyidagicha: ^{[ original tadqiqot? ]}

bo'lsin dist a | V | × | V | boshlanadi minimal masofaga ∞ (abadiy) majmuasini

har biri uchun chetiga ( U , V ) , albatta,

dist [ u ] [ v ] ← w ( u , v ) // chetiga og'irligi ( U , v )

har biri uchun uch V qilish

dist [ v ] [ v ] ← 0

uchun K dan 1 uchun | V |

uchun I dan 1 uchun | V |

uchun j dan 1 gacha | V |

agar dist [ i ] [ j ]> dist [ i ] [ k ] + dist [ k ] [ j ]

dist [ i ] [ j ] ← dist [ i ] [ k ] + dist [ k ] [ j ]

oxiri, agar

Misol [ tahrirlash ]

Yuqoridagi algoritm quyidagi chapdagi grafikda bajariladi:

Yuqoridagi k = 0 deb belgilangan tashqi ko'chadan birinchi rekursiyasidan oldin, ma'lum bo'lgan yo'llar grafadagi bitta qirralarga to'g'ri keladi. K = 1 nuqtada 1 vertikaldan o'tadigan yo'llar topiladi: xususan, [2,1,3] yo'l topilib, qirralari ozroq, ammo uzunroq (og'irlik jihatidan) ). At k = 2 , uchlari {1,2} orqali sayohat yo'llarini topilgan. Qizil va ko'k katakchalar [4,2,1,3] yo'lining oldingi iteratsiyalarda uchragan ikkita [4,2] va [2,1,3] yo'llaridan qanday qilib yig'ilganligini va 2 chorrahada qanday bo'lganligini ko'rsatadi. [2,1,3] 2 3. juda uzoq duch eng qisqa yo'ldir, chunki yo'l [4,2,3], deb hisoblanmaydi K = 3, {1,2,3} cho'qqilaridan o'tadigan yo'llar topilgan. Va nihoyat, k = 4 da , barcha eng qisqa yo'llar topiladi.

Har bir iterasyonda masofa Matrix k , yangilangan masofalarga bilan qalin , bo'ladi:

k = 0		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 1		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 2		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0

k = 3		j
		1	2	3	4
i	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	−1	1	0

k = 4		j
		1		2	3	4
i	1	0	−1		−2	0
	2	4	0		2	4
	3	5	1		0	2
	4	3	−1		1	0

Salbiy tsikllar bilan xatti-harakatlar [ tahrirlash ]

Salbiy tsikl - bu chetlari salbiy qiymatga yig'ilgan tsikl. Har qanday vertikal juftlik o'rtasida eng qisqa yo'l yo'q{\ displaystyle i}, {\ displaystyle j} manfiy tsiklning bir qismini tashkil qiladigan, chunki yo'l uzunligi {\ displaystyle i} ga {\ displaystyle j}o'zboshimchalik bilan kichik (salbiy) bo'lishi mumkin. Floyd-Uorshall algoritmi son jihatdan mazmunli chiqishi uchun manfiy tsikllar mavjud emasligini taxmin qiladi. Shunga qaramay, agar salbiy tsikllar mavjud bo'lsa, ularni aniqlash uchun Floyd-Warshall algoritmidan foydalanish mumkin. Intuisiya quyidagicha:

• 
  Floyd-Warshall algoritmi barcha vertikal juftliklar orasidagi yo'l uzunligini takroran o'zgartiradi {\ displaystyle (i, j)}, shu jumladan, qaerda {\ displaystyle i = j};
  
• 
  Dastlab, yo'l uzunligi {\ displaystyle (i, i)} nolga teng;
  
• 
  Yo'l {\ displaystyle [i, k, \ ldots, i]} Agar uning uzunligi noldan kichik bo'lsa, ya'ni tsiklni bildirsa, bu holatni yaxshilash mumkin;
  
• 
  Shunday qilib, algoritmdan so'ng, {\ displaystyle (i, i)} Agar manfiy uzunlikdagi yo'l mavjud bo'lsa, manfiy bo'ladi {\ displaystyle i} Orqaga {\ displaystyle i}.
  

Shunday qilib, Floyd-Warshall algoritmi yordamida manfiy tsikllarni aniqlash uchun yo'l matritsasining diagonalini tekshirish mumkin, va manfiy sonning mavjudligi grafikada kamida bitta salbiy tsikl borligini ko'rsatadi. ^[9] Raqamli muammolarni oldini olish uchun algoritm doirasi ichidagi yo'l matritsasining diagonalidagi manfiy sonlarni tekshirish kerak. ^[10] Shubhasiz, yo'naltirilmagan grafikada manfiy qirg'oq uning vertikal o'qlarini o'z ichiga olgan salbiy tsiklni (ya'ni yopiq yurishni) keltirib chiqaradi. Yuqoridagi barcha qirralarni hisobga olgan holda misol grafigining yo'naltirilmagan deb hisoblash, masalan, 4 - 2 - 4 ketma-ketligi weight2 og'irlikdagi tsikl.

Yo'lni qayta qurish [ tahrirlash ]

Floyd-Warshall algoritmi odatda faqat barcha juft uchlari orasidagi yo'llarning uzunligini ta'minlaydi. Oddiy modifikatsiyalar yordamida har qanday ikkita so'nggi uchi orasidagi haqiqiy yo'lni qayta qurish usulini yaratish mumkin. Garchi har bir uchidan bir-biriga vertexdan haqiqiy yo'lni saqlashga moyil bo'lsa-da, bu kerak emas va aslida xotira nuqtai nazaridan juda qimmatga tushadi. Buning o'rniga, eng qisqa yo'ldagi daraxtni har bir tugun uchun hisoblash mumkin{\ displaystyle \ Theta (| E |)} vaqt foydalanish {\ displaystyle \ Theta (| V |)} har bir daraxtni saqlash uchun xotira, bu bizga bog'langan ikki vertikaldan yo'lni samarali qayta qurish imkonini beradi.

Psevdokod ^[11] [ tahrirlash ]

bo'lsin dist a





{\ displaystyle | V | \ marta | V |}

boshlang'ich minimal masofalar qatori

{\ displaystyle \ infty}

(abadiy)

ruxsat bo'lishi keyingi bir





{\ displaystyle | V | \ marta | V |}

nolga boshlang'ich indekslarning qatori

tartibi FloydWarshallWithPathReconstruction () bo'lgan

har bir uchun (u, v) chetiga nima

dist [u] [v] ← w (u, v) // chetiga og'irligi (u, v)

keyingisi [u] [v] ← v

har bir vertex uchun v do

dist [ v ] [ v ] ← 0

keyingi [v] [v] ← v

uchun K dan 1 uchun | V | nima // standart Floyd-Warshall bajarilishini

uchun i dan 1 uchun | V |

uchun J dan 1 uchun | V |

agar dist [i] [j]> dist [i] [k] + dist [k] [j] bo'lsa

dist [i] [j] ← dist [i] [k] + dist [k] [j]

keyingi [i] [j] ← keyingi [i] [k]

tartibi yo'l (u, v)

agar keyingi [u] [v] = null keyin

qaytib ] [

yo'l = [u]

esa u ≠ v

u ← keyingi [u] [v]

path.append (u)

qaytish yo'li

Tahlil [ tahrir ]

Ruxsat bering {\ displaystyle n} bo'lmoq {\ displaystyle | V |}, vertikallarning soni. Hammasini topish uchun{\ displaystyle n ^ {2}} ning {\ displaystyle \ mathrm {shortestPath} (i, j, k)} (Barcha uchun {\ displaystyle i} va {\ displaystyle j}) dan {\ displaystyle \ mathrm {shortestPath} (i, j, k-1)} talab qiladi {\ displaystyle 2n ^ {2}}operatsiyalar. Biz boshlaganimizdan beri {\ displaystyle \ mathrm {shortestPath} (i, j, 0) = \ mathrm {edgeCost} (i, j)} va ketma-ketligini hisoblang {\ displaystyle n} matritsalar {\ displaystyle \ mathrm {shortestPath} (i, j, 1)}, {\ displaystyle \ mathrm {shortestPath} (i, j, 2)}, {\ displaystyle \ ldots}, {\ displaystyle \ mathrm {shortestPath} (i, j, n)}, ishlatilgan operatsiyalarning umumiy soni {\ displaystyle n \ cdot 2n ^ {2} = 2n ^ {3}}. Shuning uchun algoritmning murakkabligi{\ displaystyle \ Theta (n ^ {3})}.

Ilovalar va umumlashtirish [ tahrirlash ]

Floyd-Warshall algoritmidan quyidagi muammolarni echishda foydalanish mumkin, bular qatori:

• 
  Yo'naltirilgan grafikadagi eng qisqa yo'llar (Floyd algoritmi).
  
• 
  Yo'naltirilgan grafiklarning tranzit yopilishi (Warshall algoritmi). Warshall tomonidan algoritmning dastlabki shakllanishida grafika taqqoslanmagan va Boolean qo'shilish matritsasi bilan ifodalangan. Keyin qo'shimcha operatsiya mantiqiy ulanish (AND) va minimal operatsiya mantiqiy uzilish (OR) bilan almashtiriladi.
  
• 
  Chegaralangan avtomat tomonidan qabul qilingan oddiy tilni anglatuvchi oddiy iborani topish ( Kleen algoritmi , Floyd-Uorshall algoritmining chambarchas bog'liqligi) ^[12]
  
• 
  Inversiya ning real matrislerinin ( Gauss-Jordan algoritm ) ^[13]
  
• 
  Optimal marshrutlash. Ushbu dasturda ikkita tepa orasidagi maksimal oqim bilan yo'lni topish qiziqtiradi. Bu shuni anglatadiki, yuqoridagi psevdokodda bo'lgani kabi minima olishdan ko'ra, maxima olinadi. Chet eldagi og'irliklar oqimdagi qat'iy cheklovlarni anglatadi. Yo'l og'irliklari qiyinchiliklarni anglatadi; shuning uchun yuqoridagi qo'shimcha operatsiya minimal operatsiya bilan almashtiriladi.
  
• 
  Pathfinder tarmoqlarini tezkor hisoblash .
  
• 
  Eng keng yo'llar / o'tkazish qobiliyatining maksimal yo'llari
  
• 
  Tarkibiy matritsalarning kanonik shakli (DBM) hisoblash
  
• 
  Grafiklar o'rtasidagi o'xshashlikni hisoblash
  

Amalga oshirish [ tahrirlash ]

Amaliyot ko'plab dasturlash tillari uchun mavjud .

• 
  Uchun C ++ , ichida oshirish :: grafik kutubxona
  
• 
  Uchun C # da QuickGraph
  
• 
  Uchun C # da QuickGraphPCL (Portativ sinfi kitaplıkları foydalanib loyihalari bilan yaxshi muvofiqligi bilan QuickGraph bir sanchqi.)
  
• 
  Uchun Java yilda, Apache Commons chizma kutubxona
  
• 
  Uchun JavaScript -yilda, Cytoscape kutubxona
  
• 
  Uchun MATLAB bilan, Matlab_bgl to'plami
  
• 
  Uchun Perl ham, chizma modul
  
• 
  Uchun Python , ham SciPy kutubxona (modul scipy.sparse.csgraph ) yoki NetworkX kutubxona
  
• 
  Uchun R , paketlarda e1071 va Rfast
  

Boshqa qisqa yo'l algoritmlarni bilan solishtirish [ tahrir ]

Floyd-Warshall algoritmi barcha vertikal juftliklarning zich grafikdagi yo'llarini hisoblash uchun yaxshi tanlovdir , bunda ko'p yoki barcha uchlari bir-biriga bog'lab qo'yilgan. Salbiy bo'lmagan chekka og'irlikdagi grafikalar uchun har bir boshlang'ich verteksidan Dijkstra algoritmidan foydalanish afzalroqdir , chunki takroriy Dijkstra ishlagan vaqt ({\ displaystyle O (| E || V | + | V | ^ {2} \ log | V |)}Fibonachchi uyumlaridan foydalanish ) ga qaraganda yaxshiroq{\ displaystyle O (| V | ^ {3})} Floyd-Warshall algoritmining qachon ishlaydigan vaqti {\ displaystyle | E |} nisbatan ancha kichik {\ displaystyle | V | ^ {2}}. Salbiy qirralari bor, ammo manfiy tsikllari bo'lmagan siyrak grafikalar uchun Jonson algoritmidan foydalanish mumkin, bunda Dijkstra takroriy yondashish bilan bir xil asimptotik ish vaqti bor.

Zich grafiklarda barcha juft juftliklarning eng qisqa yo'llarini hisoblashni tezlashtirish uchun tezkor matritsa multiplikatsiyasidan foydalangan holda ma'lum algoritmlar mavjud , ammo ular odatda chekka og'irliklarda (masalan, kichik sonlar bo'lishini talab qilishda) qo'shimcha taxminlarni amalga oshiradilar. ^[14] [15] Bunga qo'shimcha ravishda, ularning ish vaqtidagi doimiy omillar juda katta bo'lganligi sababli, ular faqat Floyd-Warshall algoritmi orqali juda katta grafikalar uchun tezlikni ta'minlaydilar.