else

end

end

در این آزمون­ها مقدار در نظر گرفته شده است.

ج) الگوریتم دایسترا

الگوریتم دایسترا یکی از الگوریتم‌های پیمایش گراف است که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دِیْکْسْترا در سال ۱۹۵۹ ارائه شد.
این الگوریتم یکی از الگوریتم‌های پیمایش گراف است که مساله کوتاه‌ترین مسیر از یک مبدأ را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همه رأس‌هایگراف را به دست می‌دهد. هم­چنین، می‌توان از این الگوریتم برای پیدا کردن کوتاه‌ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاه‌ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

این الگوریتم، کوتاه ترین مسیر از گره S (مبدا) را به دیگر گره­ها پیدا می­ کند. الگوریتم با تخصیص مقادیر اولیه به عنوان فاصله از گره S به دیگر گره­ها شروع می شود. در هر گام الگوریتم مقدار فاصله را بهبود می بخشد.
حالت هر گره از دو مشخصه، فاصله و وضعیت مشخص می شود. فاصله هر گره در واقع یک عدد است که فاصله گره را از گره S مشخص می­ کند. وضعیت یک ویژگی است که مشخص می کند که فاصله هر گره برابر با کوتاه ترین فاصله از گره S است یا نه. اگر فاصله گره برابر با کوتاه ترین مسیر باشد آن­گاه وضعیت آن را دایمی می­گوییم. در غیر این­صورت، وضعیت را موقتی گوییم. الگوریتم به طور گام به گام وضعیت هر گره را بهبود می بخشد. در هر تکرار، گره را گره جاری قرار بده.
پارامترهای الگوریتم عبارتند از:
: مقدار فاصله گره l
p,t : وضعیت های گره، p وضعیت دایمی و t وضعیت موقتی
: هزینه سفر یال ij