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

با دانلود تحقیق در مورد تحليل مساله كوتاهترين مسير در گراف جهت دار در خدمت شما عزیزان هستیم.این تحقیق تحليل مساله كوتاهترين مسير در گراف جهت دار را با فرمت word و قابل ویرایش و با قیمت بسیار مناسب برای شما قرار دادیم.جهت دانلود تحقیق تحليل مساله كوتاهترين مسير در گراف جهت دار ادامه مطالب را بخوانید.

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

فرمت فایل:word و قابل ویرایش

تعداد صفحات فایل:10 صفحه

قسمتی از فایل:

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

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

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

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

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

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

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

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