Taqsimlangan algoritmlar va tizimlar” fanidan mustaqil ish №3

qaytish yo'li

Tahlil.

Mayli{\displaystyle n} bo'l{\displaystyle |V|} , uchlari soni. Hammasini topish uchun{\ Displaystyle n ^ {2}} ning {\displaystyle \mathrm {shortestPath} (i,j,k)} (Barcha uchun{\displaystyle i} va{\displaystyle j} ) ulardan {\displaystyle \mathrm {shortestPath} (i,j,k-1)} talab qiladi{\displaystyle 2n^{2}} operatsiyalar. Biz bilan 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)} , foydalanilgan operatsiyalarning umumiy soni {\displaystyle n\cdot 2n^{2}=2n^{3}} . Shuning uchun algoritmning murakkabligi{\ displaystyle \ Theta (n ^ {3})} .

Ilovalar va umumlashtirishlar.

Floyd-Uorshall algoritmi boshqa muammolarni hal qilish uchun ishlatilishi mumkin:

• 
  Yo'naltirilgan grafiklardagi eng qisqa yo'llar (Floyd algoritmi).
  
• 
  Yo'naltirilgan grafiklarning tranzitiv yopilishi (Uorshall algoritmi). Uorshallning algoritmning asl formulasida grafik vaznsiz va mantiqiy qo'shnilik matritsasi bilan ifodalanadi . Keyin qo‘shish amali mantiqiy konyunksiya (AND) va minimal amal mantiqiy ayirma (OR) bilan almashtiriladi.
  
• 
  Cheklangan avtomat tomonidan qabul qilingan muntazam tilni bildiruvchi muntazam iborani topish ( Kleen algoritmi , Floyd-Uorshall algoritmining chambarchas bog'liq umumlashmasi) ^[12]
  
• 
  Haqiqiy matritsalarning inversiyasi ( Gauss - Iordaniya algoritmi ) ^[13]
  
• 
  Optimal marshrutlash. Ushbu ilovada ikkita cho'qqi orasidagi maksimal oqim bilan yo'lni topish qiziqtiradi. Bu shuni anglatadiki, yuqoridagi psevdokodda bo'lgani kabi minimani olish o'rniga, maksimal qiymatni oladi. Chet og'irliklari oqimdagi qat'iy cheklovlarni ifodalaydi. Yo'l og'irligi to'siqlarni ifodalaydi; shuning uchun yuqoridagi qo'shish amali minimal operatsiya bilan almashtiriladi.
  
• 
  Pathfinder tarmoqlarini tez hisoblash .
  
• 
  Eng keng yo'llar/Maksimal tarmoqli kengligi yo'llari
  
• 
  Farqi bilan bog'langan matritsalarning kanonik shaklini hisoblash (DBM)
  
• 
  Grafiklar orasidagi o'xshashlikni hisoblash
  
• 
  VA/YOKI/eshik grafiklarida o‘tish davri yopilishi. ^[14]