View Full Version : سوال: الگوریتم یافتن تک تک مسیرها برای خروجی فلویید
zohreh152j
سه شنبه 20 اسفند 1387, 09:28 صبح
با سلام و خسته نباشی الگوریتمی نیاز دارم که ماتریس p خروجی فلویید را بگیرد وتک تک مسیر ها را برای رفتن از i به j را چاپ کند
pesar irooni
چهارشنبه 21 اسفند 1387, 23:09 عصر
اگر ماتریس ماقبل (فرضا 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
چهارشنبه 21 اسفند 1387, 23:12 عصر
ضمنا نقاط توقفش هم میشه :
Lij(0) = { nil if Wij=infinite or i=j , i if wij < infinite and i !=j }
vBulletin® v4.2.5, Copyright ©2000-1403, Jelsoft Enterprises Ltd.