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

0 6.6k

لینک کوتاه https://razzaghi.pdf-doc.ir/p/6eba5b5 |

با دانلود تحقیق در مورد تحليل مساله كوتاهترين مسير در گراف جهت دار در خدمت شما عزیزان هستیم.این تحقیق تحليل مساله كوتاهترين مسير در گراف جهت دار را با فرمت 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) داشته باشند شروع ميشوند .

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