تبدیل آلگوریتم بازگشتی به غیر بازگشتی

[آنیل]

توی الگوریتم فلوید علاوه بر ماتریسی که هزینه کوتاهترین مسیر بین هر
دوتا نود ذخیره میکنه ماتریس دیگه ای ساخته میشه که نودهای کوتاهترین
مسیر بین هر دوتا نود نگه میداره.ماتریس p
حالا اگه بخوایم کوتاهترین مسیر بین دوتا نود خاص پیدا کنیم این ماتریس
میدیم به الگوریتم زیر:


function Path(i,j,)
{
if( p1[i][j] == -1 )
{

print i,j;
return
}
else
{
Path ( i,p[i][j] )
Path( p[i][j ],j) h


{

{
میخواستم بدونم میتونید این الگوریتم به غیر بازگشتی تبدیل کنید به طوری
که آخر کار نود های میانی مسیر بین دوتا نود آرگومان رو تو یه آرایه یک بعدی
ذخیره کنه؟ و اون آرایه رو برگردونه؟
یا الگوریتم غیر بازگشتی دیگه دارید که همین کار رو بکنه؟

[qwerty11]

فکر نمیکنم بشه براش الگوریتم غیر بازگشتی خاصی پیدا کرد، مگر اینکه اون الگوریتم بازگشتی هم از stack استفاده کنه.

اگر هدفتون پیدا کردن مسیر بین فقط و فقط 2 تا گره هستش و در واقع فقط یه query دارین پیشنهاد میکنم از dijkstra استفاده کنین. و برای هر گره یه فیلد parent در نظر بگیرید و به صورت معکوس از مقصد به سمت مبدا بیاید. این شکلی :


int v=destination, i=0;
while(v!=source){
route[i++]=v;
v=parent[v];
}