Taqsimlangan algoritmlar va tizimlar” fanidan mustaqil ish №3

Yo'lni qayta qurish.

Floyd-Uorshall algoritmi odatda faqat barcha cho'qqilar juftlari orasidagi yo'llarning uzunligini ta'minlaydi. Oddiy modifikatsiyalar yordamida har qanday ikkita oxirgi nuqta cho'qqilari orasidagi haqiqiy yo'lni qayta qurish usulini yaratish mumkin. Har bir cho'qqidan bir-birining cho'qqisiga haqiqiy yo'lni saqlashga moyil bo'lishi mumkin bo'lsa-da, bu shart emas va aslida xotira jihatidan juda qimmat. Buning o'rniga, har bir tugun uchun eng qisqa yo'l daraxtini hisoblash mumkin{\ displaystyle \ Theta (|E|)} vaqtdan foydalanish{\ displaystyle \ Theta (|V|)} Har bir daraxtni saqlash uchun xotira, bu bizga har qanday ikkita bog'langan cho'qqidan yo'lni samarali tarzda qayta qurish imkonini beradi.

Psevdokod.

dist a bo'lsin


{\ displaystyle |V|\times |V|}

ishga tushirilgan minimal masofalar massivi


{\displaystyle \infty}

(cheksizlik)
keyingi a bo‘lsin


{\ displaystyle |V|\times |V|}

null ga ishga tushirilgan tepalik indekslari massivi


FloydWarshallWithPathReconstruction () protsedurasi har
bir chekka uchun (u, v) do
dist[u][v] ← w(u, v) // Kenarning og'irligi (u, v)
keyingi[u][v] ← v
har bir v nuqtasi uchun do
dist[v][v] ← 0
keyingi[v][v] ← v
k uchun 1 dan |V| gacha do // 1 dan |V|
gacha bo'lgan i uchun Floyd-Warshall standart dasturi
j uchun 1 dan |V|
gacha agar dist[i][j] > dist[i][k] + dist[k][j] keyin
dist[i][j] ← dist[i][k] + dist[k][j]
keyingi[i][j] ← keyingi[i][k]
protsedura Yo'l(u, v)
agar keyingi[u][v] = null bo'lsa, [] ni
qaytaring
yo'l = [u]
esa u ≠ v
u ← keyingi[u][v]
path.append(u)