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

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