Taqsimlangan algoritmlar va tizimlar” fanidan mustaqil ish №3

Tarix va nomlash.

Floyd-Uorshall algoritmi dinamik dasturlashning namunasidir va Robert Floyd tomonidan 1962 yilda e'tirof etilgan shaklda nashr etilgan . ^[3] Biroq, u asosan Bernard Roy tomonidan 1959 yilda nashr etilgan algoritmlar bilan bir xil ^[4] va shuningdek, Stiven Uorshall tomonidan 1962 yilda ^[5] grafikning oʻtishli yopilishini topish uchun ^[6] va deterministik chekli avtomatni muntazam ifodaga aylantirish uchun Kleenning algoritmi (1956 yilda nashr etilgan) bilan chambarchas bogʻliq . ^[7]Algoritmning uchta ichki o'rnatilgan for-loop sifatidagi zamonaviy formulasi birinchi marta Piter Ingerman tomonidan 1962 yilda tasvirlangan ^[8].

Algoritm.

Floyd-Uorshall algoritmi har bir juft cho'qqi orasidagi grafik orqali barcha mumkin bo'lgan yo'llarni solishtiradi. Bu bilan buni qilishga qodir{\ displaystyle \ Theta (|V|^{3})} gacha bo'lishi mumkin bo'lsa ham, grafikdagi taqqoslashlar{\displaystyle \Omega (|V|^{2})} Grafikdagi qirralar va qirralarning har bir birikmasi tekshiriladi. Bu ikki cho'qqi orasidagi eng qisqa yo'l bo'yicha bahoni optimal bo'lgunga qadar bosqichma-bosqich yaxshilash orqali amalga oshiradi.
{\displaystyle \mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )}} .
Ushbu formula Floyd-Uorshall algoritmining markazidir. 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 jarayongacha davom etadi{\displaystyle k=N} , va biz hamma uchun eng qisqa yo'lni topdik{\displaystyle (i,j)} har qanday oraliq uchlari yordamida juftlash. Ushbu asosiy versiya uchun psevdokod quyidagicha:
dist |V| bo'lsin × |V| har bir chekka ( u , v ) do
dist[ u ][ v ] ← w( u , v ) uchun ∞ (cheksizlik) ga ishga tushirilgan minimal masofalar massivi
// Har bir v do tepasi uchun chetning ogʻirligi ( u , v )
dist[ v ][ v ] ← 0
k uchun 1 dan |V|