پاورپوینت کامل کوتاه‌ترین مسیر بین تمامی زوج راس‌ها ۵۷ اسلاید در PowerPoint

توجه : این فایل به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل کوتاه‌ترین مسیر بین تمامی زوج راس‌ها ۵۷ اسلاید در PowerPoint دارای ۵۷ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

شما با استفاده ازاین پاورپوینت میتوانید یک ارائه بسیارعالی و با شکوهی داشته باشید و همه حاضرین با اشتیاق به مطالب شما گوش خواهند داد.

لطفا نگران مطالب داخل پاورپوینت نباشید، مطالب داخل اسلاید ها بسیار ساده و قابل درک برای شما می باشد، ما عالی بودن این فایل رو تضمین می کنیم.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی پاورپوینت کامل کوتاه‌ترین مسیر بین تمامی زوج راس‌ها ۵۷ اسلاید در PowerPoint،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از مطالب داخلی اسلاید ها

پاورپوینت کامل کوتاه‌ترین مسیر بین تمامی زوج راس‌ها ۵۷ اسلاید در PowerPoint

اسلاید ۴: فرض مساله شبکه، قویاً همبند است. در شبکه قویاً همبند، از هر گره به تمامی گره های دیگر یک مسیر جهت دار وجود دارد.به راحتی می توانیم این شرط را برقرار کنیم.با انتخاب یک راس دلخواه (s)، و افزودن یالهای (s, i) و (i , s ) با هزینه های به اندازه کافی بزرگ به ازای راسهایi N- {s} (در صورتی که یال مربوطه نباشد)شبکه شامل دور منفی نیست.۴

اسلاید ۵: الگوریتم Shortest Path Repeatedحالت اول : شبکه شامل یال با طول منفی نیست.در این حالت با n باراجرای الگوریتم Single Shortest Path می توانیم مساله را حل کنیم. ( هر بار یکی از گره ها را به عنوان منبع انتخاب میکنیم.)حالت دوم : شبکه شامل یال هایی با طول منفی است.در این حالت، ابتدا شبکه را به یک شبکه با طول های غیر منفی تبدیل می کنیم. سپس الگوریتم Single Shortest Path را برای هر کدام از رئوس اجرا می کنیم.۵

اسلاید ۶: الگوریتم Shortest Path Repeatedطریقه تبدیل شبکه به شبکه ای با طولهای غیرمنفی: ابتدا یک گره را به عنوان گره مبدا(s) انتخاب می کنیم . سپس الگوریتم FIFO Label Correcting را اجرا می کنیم. در این صورت کم ترین فاصله از راس s تا همه رئوس دیگر محاسبه می شود.با اجرای الگوریتم FIFO Label Correcting یا الگوریتم یک دور منفی را تشخیص می دهد. در این حالت مساله کوتاه ترین مسیر بین زوج راس ها جواب ندارد. یا برای همه رئوس کوتاهترین مسیراز راسs را محاسبه می کند (d(j)). در این حالت برای هر یال، طول کاهش یافته را به صورت زیرمحاسبه می کنیم:۶

اسلاید ۷: تبدیل شبکه به شبکه ای با طولهای غیرمنفی شبکه با طول کاهش یافته را تشکیل می دهیم. در این حالت: بنابراین شبکه به شبکه ای با طول های غیر منفی تبدیل شد. در شبکه کاهش یافته الگوریتم Single Shortest Path را برای n تا راس اجرا می کنیم. درشبکه بدست آمده به مقدارکوتاه ترین فاصله بین دو راس lو k مقدار زیر را اضافه می کنیم تا مقدار واقعی کوتاه ترین فاصله در شبکه اولیه حاصل شود. ۷

اسلاید ۸: زمان اجرای الگوریتمزمان تبدیل شبکه به شبکه با طول های غیر منفی : زمان اجرای الگوریتم FIFO Label Correcting : O(mn) زمان اجرای الگوریتم Single Shortest Path: S(n,m,C) با n با اجرای Single Shortest Path : O(n * S(n,m, C)) زمان اجرای الگوریتم :O(n* S(n,m,C) = O(m * n + n * S(n,m, C)) 8

اسلاید ۹: قضیه الگوریتم repeated shortest path کوتاه ترین مسیر بین زوج راس ها را در زمان O(n* S(n,m,C) حل می کند.۹

اسلاید ۱۰: ۲۱۳۴۵۱۹۳۴-۲ مثال-۲۱۰

اسلاید ۱۱: ۲۱۳۴۵۱۹۳۴-۲۰ مثال -۲۱۱

اسلاید ۱۲: ۲۱۳۴۵۱۹۳۴-۲۰ مثال-۲۱۲

اسلاید ۱۳: ۲۱۳۴۵۱۹۳۴-۴۰۳ مثال -۲۱۳

اسلاید ۱۴: ۱۹۳۴-۲۰-۲۳۱۲۳۴۵ مثال -۲۱۴

اسلاید ۱۵: ۱۹۳۴-۲۰۷-۲۳۱۲۳۴۵ مثال-۲۱۵

اسلاید ۱۶: ۱۹۳۴-۲۰۷-۲۳۵۱۲۳۴۵ مثال -۲۱۶

اسلاید ۱۷: ۱۹۳۴-۲۰۷-۲۳۲۱۲۳۴۵ مثال -۲۱۷

اسلاید ۱۸: ۱۹۳۴-۲۷-۲۳۲۰۱۲۳۴۵ مثال-۲۱۸

اسلاید ۱۹: ۱۹۳۴-۲۷-۲۳۲۰۱۲۳۴۵ مثال -۲۱۹

اسلاید ۲۰: مثال۲۱۳۴۵۱۹۳۴-۲۷-۲۳۲۰-۲۲۰

اسلاید ۲۱: مثال۲۱۳۴۵۱۹۳۴-۲۷-۲۳۲۰۰۰۰۲۳۰-۲۲۱

اسلاید ۲۲: مثالبنابراین شبکه به شبکه ای با طول های غیر منفی تبدیل شد.فاصله راس ۱و ۲ :۰ فاصله در شبکه اصلی : ۰ -۰ +(-۲)= -۲فاصله راس ۱و۵ : ۰فاصله در شبکه اصلی :۰-۰+۲=۲۲۱۳۴۵۰۷-۲۳۲۰۰۰۰۲۳۲۲

اسلاید ۲۳: الگوریتم All-Pairs Generic Label-correctingفرض کنید [i , j] نشانگر زوج راس iو j در شبکه باشد.در الگوریتم All-Pairs Label-correcting ،