تازه ها
الگوریتم کوتاهترین مسیر به روش فلوید
الگوریتم های زیادی برای بدست آوردن کوتاه ترین مسیر در یک گراف مسطح و وزن دار وجود دارد.که ما دو الگوریتم فلوید و دایجسترا را شرح می دهیم.
الگوریتم فلوید:در این الگوریتم هر بار یک گره به عنوان مبداء، یک گره به عنوان واسط و یک گره به عنوان مقصد تعیین می شود.این الگوریتم از سه حلقه ی 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)
