برای شما بازدید کننده محترم این مقاله کامل را تهیه کرده ایم.

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

قسمتی از متن :

1

‏تحليل ‏مساله ‏كوتاهترين مسير در گراف‏ جهت دار

‏اگر ‏ يك گراف جهت دار باشد فرض كنيد هر لبه ‏ با وزن ‏ مشخص مي گردد و هزينه رفتن مستقيم از گره i‏ به j‏ را مشخص ميسازد بزودي الگوريتم دايجسترا را كه براي يافتن كوتاهترين مسير در گراف با وزن هاي مثبت كاربرد دارد را بيان ميكنيم . در این بخش و بخش بعدي دو مساله مرتبط با گراف را بيان خواهيم كرد .

‏1 ) گراف G‏ را در نظر بگيريد ( وزن دار ) اگر این گراف داراي سيكل منفي باشد آنگاه يك سيكل جهت دار c‏ مثل :

‏2) اگر گراف شامل هيچ دوره ( سيكل‏‌‏)‏‌‏ منفي نباشد يافتن مسيري به نام p‏ از گره آغازي s‏ و گره پاياني t‏ با كمترين هزينه :‏ ‏ ‏بايد كمترين باشد به ازاي هر مسير از s‏ به t‏ . این مساله به هر دو نام مسير با كمترين هزينه و كوتاهترين مسير ناميده مي شود .

‏طراحي و آناليز الگوريتم :

‏اكنون با شروع تعريف مجدد الگوريتم دايجسترا كه براي يافتن كوتاهترين مسير در گراف هايي كه وزن منفي ندارند شروع ميكنيم .

2

‏در این گراف يك مسير از s‏ به t‏ با ملاقات چندين دفعه دوره ( سيكل ) C‏ بدست مي آيد .

‏كوتاهترين مسير با شروع از گره آغازين s‏ به هر نود v‏ در يك گراف اصولا يك الگوريتم حريصانه است . ايده اصلي از يك مجموعه S‏ تشكيل شده است كه كوتاهترين مسير از هر نود s‏ به هر نود داخل مجموعه S‏ شناخته شده است . در این شكل این الگوريتم را نشان مي دهيم با ‏ شروع ميكنيم . ما ميدانيم كوتاهترين مسير از s‏ به s‏ داراي هزينه صفر است زمانيكه هيچ لبه با وزن منفي نداشته باشيم . سپس این عنصر را به طور حريصانه به مجموعه اضافه ميكنيم . در طي مرحله اول الگوريتم حريصانه ما كمترين هزينه لبه هاي گره s‏ را تشكيل خواهيم داد . بعبارت ديگر يعني : ‏ . يك نكته مهم با توجه به الگوريتم دايجسترا این است كه كوتاهتري مسير از s‏ به v‏ با يك يال ‏ نمايش داده مي شود بنابراين بلافاصله نود v‏ را به مجموعه S‏ اضافه ميكنيم . پس مسير ‏ مسلما كوتاهترين مسير به v‏ است اگر هيچ يالي با هزينه منفي نداشته باشيم . مسير هاي ديگر از s‏ به v‏ بايد از يك يال خارج شده از s‏ كه حداقل هزينه بيشتري نسبت به لبه (s,v)‏ داشته باشند شروع ميشوند .

‏این ايده همواره صحيح نيست بويژه زماني كه داراي لبه هاي با وزن منفي هستيم .

تصاویری از چند صفحه نخست فایل :

توجه فرمایید بدلیل تهیه ی تصویر با نرم افزار های خارجی متن نمایش داده شده در تصاویر ممکن است دارای اشکالاتی در نمایش برخی حروف باشد که در فایل اصلی بدون مشکل است