591 - تحلیل مساله کوتاهترین مسیر در گراف جهت دار

591 - تحلیل مساله کوتاهترین مسیر در گراف جهت دار

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

                  فرمت فایل:   ورد – Word و قابل ویرایش تعداد صفحات: 12          اگر   یک گراف جهت دار باشد فرض کنید هر لبه   با وزن   مشخص می گردد و هزینه رفتن مستقیم از گره i به j را مشخص میسازد بزودی الگوریتم دایجسترا را که برای یافتن کوتاهترین مسیر در گراف با وزن های مثبت کاربرد دارد را بیان میکنیم . در این بخش و بخش بعدی دو مساله مرتبط با گراف را بیان خواهیم کرد . 1 ) گراف G را در نظر بگیرید ( وزن دار ) اگر این گراف دارای سیکل منفی باشد آنگاه یک سیکل جهت دار c مثل :   2) اگر گراف شامل هیچ دوره ( سیکل‌)‌ منفی نباشد یافتن مسیری به نام p از گره آغازی s و گره پایانی t با کمترین هزینه :   باید کمترین باشد به ازای هر مسیر از s به t . این مساله به هر دو نام مسیر با کمترین هزینه و کوتاهترین مسیر نامیده می شود . طراحی و آنالیز الگوریتم : اکنون با شروع تعریف مجدد الگوریتم دایجسترا که برای یافتن کوتاهترین مسیر در ...