خبرگزاری آیصد (جدیدترین و جذاب ترین اخبار ایران و جهان)

نشر توسط:admin Views 51 تاریخ : 2 خرداد 1395

الگوریتم های زیادی برای بدست آوردن کوتاه ترین مسیر در یک گراف مسطح و وزن دار وجود دارد.که ما دو الگوریتم فلوید و دایجسترا را شرح می دهیم.

الگوریتم فلوید:در این الگوریتم هر بار یک گره به عنوان مبداء، یک گره به عنوان واسط و یک گره به عنوان مقصد تعیین می شود.این الگوریتم از سه حلقه ی for تودرتو تشکیل شده.حلقه ی for بیرونی شمارنده ای برای گره ی واسط است.حلقه ی for  درون آن شمارنده ای برای گره مبداء و حلقه ی درونی آن نیز شمارنده ای برای گره مقصد است.

برای مثال اگر قرار است از از نود 3 با واسط نود2 به نود5 برویم،مینیمم وزن یال های (2،5)+ (3,2)و(3،5)به عنوان وزن یال(3،5) قرار می گیرد.

[(C(i,j)=Min[C(i,j),c(i,k)+c(k,j

حال اگر قرار باشد نقطه(3،6) با واسط 5 را بررسی کنیم

[(C(3,6)=min[c(3,6),c(3,5)+c(5,6

در این صورت مقدار (c(5,3  از قبل مشخص شده حال چه با واسط چه بی واسط.

بررسی مرتبه زمانی الگوریتم:

توجه کنید که در این الگوریتم ما کوتاهترین مسیر بین همه جفت گره ها را پیدا می کنیم.در واقع وجود سه حلقه ی for تودرتو به خاطر همین است.

O(n^3)