نام فایل : تحليل مساله كوتاهترين مسير در گراف جهت دار 10 ص

فرمت : .doc

تعداد صفحه/اسلاید : 9

حجم : 100 کیلوبایت

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


بايد كمترين باشد به ازاي هر مسير از
s
...