شنبه 27 آبان 1396 | Saturday 18 th of November 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
الگوریتم فلوید

مسأله کوتاهترین مسیر یک مسأله بهینه سازی است.برای هر مسئله بهینه سازی ممکن است بیش از یک حل وجود داشته باشد. با توجه به نوع مسئله بهینه سازی ، مقدار بهینه میتواند حداقل یا حداکثر به خود بگیرد.

در مورد مسئله کوتاهترین مسیر هدف یافتن کوتاهترین مسیر از یک رأس به رأس دیگر است به طوری که مسیر پیدا شده ، کوتاهترین مقدار ممکن را داشته باشد. مسئله ما یافتن هریک از این کوتاهترین مسیر هاست.

برای حل مسأله کوتاهترین مسیر ، مرحله بندی ذیل را ارائه می دهیم :

مرحله صفر ، داده های اولیه : هیچ عمل خاصی انجام نخواهد شد لیکن ماتریس وزن ، که وزن ارتباط مستقیم هر زوج رأس را تعیین می کند را به عنوان مرحله صفر در نظر می گیریم. ماتریس وزن در واقع ارزش ارتباطی کلیه زوج گره هاست با این محدودیت که در هر مسیر تنها دو رأس وجود دارد.

مرحله یک  مسیر بهینه : مجموع وزن کلیه مسیرهایی را که از رأس اول می گذرد و کوتاهترین مقدار را داشته باشد . مسیرهایی را که در این مرحله ایجاد می شوند هریک حداکثر سه رأس خواهند داشت.

مرحله دوم مسیر بهینه : مجموع وزن کلیه مسیرهایی که از رأس اول و دوم میگذرند و کوتاهترین مقدار را داشته باشند. مسیرهایی که در این مرحله ایجاد می شوند هریک حداکثر چهر رأس خواهند داشت.

مرحلهn – 1  مسیر بهینه : مجموع وزن کلیه مسیرهایی که از رأس مبدأ شروع و به رأس مقصد ختم می شوند و کوتاهترین مقدار را داشته باشد . در ضمن از کلیه رأس ها نیز بگذرد.

حال ساختار الگوریتم را توضیح  می دهیم. ابتدا ماتریس Dرا برابر ماتریس  Wقرار می دهیم، بنابراین خواهیم داشت :

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26