الگوریتم یافتن تک تک مسیرها برای خروجی فلویید

[zohreh152j]

با سلام و خسته نباشی الگوریتمی نیاز دارم که ماتریس p خروجی فلویید را بگیرد وتک تک مسیر ها را برای رفتن از i به j را چاپ کند

[pesar irooni]

اگر ماتریس ماقبل (فرضا L) را داشته باشیم که کار راحت است و گرنه باید از روی ماتریس جواب، ماتریس L را بدست بیاریم و سپس با استفاده از رابطه بازگشتی زیر تمام مسیر ها رو بدست بیاریم.
ماتریس L رو از ماتریس جواب میتوان با رابطه های بازگشتی زیر بدست آورد:

Lij(K) = { Lij(k-1) if Dij(k-1) <= Dik(k-1)+Dkj(k-1) , Lkj(k-1) if Dij(k-1) > Dik(k-1)+Dkj(k-1)

[pesar irooni]

ضمنا نقاط توقفش هم میشه :

Lij(0) = { nil if Wij=infinite or i=j , i if wij < infinite and i !=j }