علوم مهندسیمهندسی صنایع و مواد ریاضیعلوم پایه

کوتاه‌ترین مسیر بین تمامی زوج راس‌ها

صفحه 1:

صفحه 2:
مساله کوتاه ترین مسیربین تمامى زوج راس ها #تعریف مساله Shortest Path 860۵۵۲60 ‏#الگوریتم‎ All-Pairs Generic Label-correcting ‏"الگوریتم‎ ‏#امقایسه دوالگوریتم‎

صفحه 3:
تعریف مساله # در مساله کوتاه ترین مسیر بين زوج راس هاء فاصله كوتاه ترين مسير بين هردو راس در شبكه تعيين مى شود. de ‏حل‎ ol, ¥ الگوریتم ‎Shortest Path Repeated‏ !2 الگوریتم برای شبکه های خلوت (603۲56) مناسب است. 7 الگوریتم ‎All-Pairs Label-correcting‏ این الگوریتم برای شبکه های متراکم (016۲156) مناسب است.

صفحه 4:

صفحه 5:
Ghortest Pak Repected ‏الگوریتم‎ # حالت اول : شبکه شامل یال با طول منفی نیست. در این حالت با 0 باراجرای الگوریتم ۳۵1 5۱0۲65 ‎٩۱۳916‏ می توانیم مساله را حل کنیم. ( هر بار یکی از گره ها را به عنوان منبع انتخاب میکنیم) حالت دوم : شبكه شامل یال هايى با طول منفی است. در اين حالت, ابتدا شبکه را به یک شبکه با طول هاى غير منفى تبديل مى كنيم. سيس الگوریتم ۴۵۸ 5۳0۲651 90916 را برای هر کدام از رئوس اجرا می کنیم.

صفحه 6:
الگوریتم لهع؟) اه۳) اعصصسظ) طریقه تبدیل شبکه به شبکه ای با طولهای غیرمنفی: ابتدا یک گره را به عنوان گره مبدا(5) انتخاب می کنیم . سپس الگوریتم ‎FIFO Label Correcting‏ را لجرا می‌کنيم در لیرصورتکم تریرف اصله از رلس5 تاهمه رئوس‌دیگر محاسبه می‌شود. ‏#8 با اجرای الگوریتم 60۳۲661۳9 ۱۵06۱ ‎FIFO‏ ‎۲ ۲ ۲. ۳ ‏الگوريتم یک دور منفی را تشخیص می‎ Y ‏مسير بين زوج راس ها جواب ندارد.‎ ‏یا برای همه رئوس كوتاهترين مسيراز راس5 را محاسبه مى كند (([)0). در اين حالت براى هر يال. طول كاهش يافته را به صورت زيرمحاسبه مى كنيم: ‎ch = cy + di) — d(j)

صفحه 7:
‎Ree 8 1 5‏ تبديل شبكه به شبكه اى با طولهاى غيرمنفى * شبکه با طول کاهش یافته را تشکیل می دهیم. در ان حالت: | 0 ح وه بنابراین شبکه به شبکه ای با طول های غیر منفی تبدیل شد. "" در شبکه کاهش يافته الگوریتم ۳۵۲ 5۳0۲۲65 51۳0916 را برای ۲ تا راس اجرا می کنیم. #ادرشبکه بدست آمده به مقدارکوتاه ترین فاصله بین دو را از ۶۰۴ ۰ ( ‏اضافه می کنیم تا مقدار واقعی کوتاه ترین فاصله در شبکه اولیه حاصل شود. ‎400 - 0

صفحه 8:
زمان اجرای الگوریتم “أزمان تبديل شبكه به شبکه با طول هاى غير منفى زمان اجرای الگوربتم : ‎FIFO Label Correcting‏ ‎O(mn)‏ ‘Single Shortest Path ,=j5 ‏#ازمان اجرای‎ S(n,m,C) : Single Shortest Path ‏#با 0 با اجرای‎ O(n * S(n,m, C)) ‏زمان اجرای الگوریتم‎ O(n* S(n,m,C) = O(m *n + n * S(n,m, C))

صفحه 9:
الگوریتم ‎st path‏ و رادر زمان ( 030/6 0

صفحه 10:

صفحه 11:

صفحه 12:

صفحه 13:

صفحه 14:

صفحه 15:

صفحه 16:

صفحه 17:

صفحه 18:

صفحه 19:

صفحه 20:

صفحه 21:

صفحه 22:

صفحه 23:
Ol-Puircs Beceriv bubel-oorreviticy ‏الگوربتم‎ * فرض کنید از , أ] نشانگر زوج راس أو [ در شبکه باشد #ادر الگوریتم ۱۵061-0۲۲69 ۰۸۵۱۱-۳۵۱۲5 مقدار [ز, 011 نشان گر فاصله بين دو راس است. اين برجسب. طول كشت جهتدار از كره أ به كره [ است. و هم جنين حد بالاى طول كوتاه ترين مسير از راس أ به [ است. 53

صفحه 24:
شرایط بهینگی کوتاه ترین مسير بين زوج راس ها “ا قضيه : برای هر زوج راس های [ز, [] ۱۷*۷ >. فرض کنید [[, أ]0 نشانكر طول یک مسیر جهتدار از راس | به [ باشد. اين مقادیر , فواصل کوتاه ترين مسير بين زوج راس ها را نشان می دهد. اگر و تنها اگر شرط بهینگی زیر بر قرار باشد. d{i, j]<= d[i,k] + d[k,j] for all nodes i, j and k 24

صفحه 25:
شرايط بهينكى كوتاه ترين مسير بين زوج راس ها "طرف اول : فرض مى كنيم ماتريس (] طول كوتاه ترين مسير بين زوج راس ها بأشدادر اي ‎ye‏ ‎all nodes i, j and k‏ ۶۵۲ [زا]۵ + ,]0 ع>[ز ,]0 ۳ اثبات : فرض می کنیم شرط حکم برقرار نباشد. []۵ + ,]۵ < از ,ناه در این صورت اجتماع کوتاه ترین مسیر جهتدار از راس آبه | و > به [یک گشت جهت داربه طول [[,0]1 + [,0]1 از راس آبه است. 25

صفحه 26:
چندین دور

صفحه 27:
و چندین دور

صفحه 28:
آثبات شرایط بهینگی چون دور با ول مفی داريم رین طول مسیر ‎ADK] + lke f] stir P‏ ‎a)‏ طبق فرض داریم : [[,0]10 + [۵]1,1 < از ,نا در تیه لول مسب ‎Se ii, JP‏ 6 | 1 ۵ ۱ — مسیر جهت دار ‎P‏ دور جهت دار 28

صفحه 29:
ay

صفحه 30:
اثبات شرایط بهینگی #! طرف دوم: # فرض می کنیم شرط زیر بر قرار باشد. ‎and k‏ | ,۱ ۱۵065 اج ۲۵۲ [زاآ۵ + [,0]1 <>[ز ,اآل ۲ @ باید اثبات کنیم [ژ, ]0 طول کوتاهترین فاصله از مسیر أبه [ است. “ا اثبات : فرض می کنیم ۴ یک مسیر جهت دار به طول [[,0]1 به صورت زیر باشد. زو ون - وا - نز 30

صفحه 31:
اه + ی > لاک + رفك > ‎Alin id‏ > الاك ling i) S Coy, + ‏لاملا‎ dist, bd S Cuan.

صفحه 32:

صفحه 33:
در این الگوریتم مقدار [ژ ,]0 تا زمانی که شرط بهینگی ب شود ۳ ‎algorithm all-pairs label-correcting;‏ begin set ofl, ): = for all, JEN x N; set oi i]: = ۱: for each (i,j) € Ado dij) : = oy; while the network contains three nodes jj, and k 5 satistying ofl, f] > afl, K] + dfk, j] do ofl, (۰ ۶ afi, ۲ ][: end; Figure 5.6 Generic all-pairs label-correcting algorithm,

صفحه 34:
آثبات درستی الگوریتم 8 در هر مرحله از الگوریتم ۵ه > از , ال لب تیا 00000003 از گره 1 به کره زاس این گشت به یک مسیر جهت دار و چندین دور جهت دار تجزیه شود 8 هیچ کدام از دور ها نمی توانند طول مثبت داشته باشند ۰ (در غیر این صورت بهینگی [ [ , 1]1) برقرار نمی شود) پس دورها طول صفر دارند. #در نتيجه مسیر ۳ طول [ ژٌ, 0]1 دارد.. و شرط بهینگی مساله را هم دارد و اتمام الكوريتم مقادير[ ل, 0]1 طول كوتاهترين مسيرها را نشان می دهند. 34

صفحه 35:
"1 در هر تکرار مدا[ ]0 کاهش ء زمان اجرای الگوریتم (6 است

صفحه 36:
الگوریتم فلوید وارشال 68 حالت خاصی از الگوریتم 60۳۲661۳9 ‎All-Pairs Generic Label-‏ است. 8 از تکنیک برنامه نویسی بویا استفاده ۲۳ ‎atti /‏ فرك ‎ey‏ نشانكر طول كوتاه ترين مسير از راس | به راس [ باشد که فقط از رئوس ۵ [ز.:]"*0۳ ...1-1 به عنوان رئوس میانی استفاده مي کند.در این صورت مقدار کوتاهترین مسیر نهایی از راس | به راس [ را نشان می دهد. 36

صفحه 37:

صفحه 38:
ریتم فلوید وارشال algorithm Floyd-Warshall;, begin for all node pairs {i, ] € N x Ndo ii, j]: = mand predfi, ۰ for all nodes i € Ndo afi, 1 ۰: = 0; for each arc (i, ‏زر‎ € Ado d{i,/]: = cjand predii, J): = i; foreach k: = 1 tondo for each [i, [ © N x Ndo ‏از‎ ٩, ‏ز‎ < ۵۱ + ۷ then begin ۹:2 ۱ ۲ 0] ‏:آل‎ ‎pred /] : ۵ ۲ =0;

صفحه 39:
Us 5 تاه اهوأه 39 6۱ 0۵ 8۳۱ 8 ow تن |ه | 8۱ 8 ۵ 8 8 ان و

صفحه 40:
Us AO 6۱0۱ 8 ۱ 8 دناه ‎RB]‏ | ان | 8 86 8 اند و

صفحه 41:
Us AL oe)

صفحه 42:
Us AQ 00

صفحه 43:
Us AB ow

صفحه 44:
Us 44 6 | 6 0۱| ۲ | ۵ دن أت اجر هو انان إدم زمه

صفحه 45:

صفحه 46:
سایی دورهای منفی #ادر الگوریتم ۱۵061-60۲۳61[۳9 ۸۵۱-۴۵۱۳5 با چک کردن شروط زیر می توانیم وجود دور منفی را شناسایی کنیم. ‎Ifi = j, check whether d[i, i] < 6.‏ ,1 ‎Ifi #j, check whether d[i, j] < —nC.‏ .2 اثبات حالت اول : 0 > [1 ,]0 مى توانيم بنويسيم ‎kK] + ALK,i]‏ ,01 < 1 ,۰011 بنابراین"شبکه شامل یک گشت جهتدار از أبه کا و یک کشت جهت دار دیگر از ک ب» [ است كه مجموع طول اين كشت ها [أ,أ]0 است که عددی منفی است.اجتماع این 01 0 بسته است؛ ‎AB

صفحه 47:

صفحه 48:
حالت دوم :۳0*0- > # در این حالت شبکه. )۲۴ است.

صفحه 49:
شناسایی دورهای منفی در فلوید وارشال روش اول : در الكوريتم فلويد وارشال با جك كردن شرط < ‎٠‏ [0]1,1ميتوانيم وجود دور منفى را تشخيص دهيم. می توانیم ثابت کنیم اگر دور منفی داشته باشیم هميشه 0 > [,0]1 خواهد بود. روحق دوم : می توانیم با استفاده از گراف 0۲60666550۲ وجود دور منفی را تشخیص دهيم. در صورتى كه شبكه دور منفى نداشته باشد كراف 0۲60666550۲ یک درخت خواهد بود. ولى در حالتى كه شبكه دور منفى داشته باشد كراف ۲ دور خواهد داشت. ‎O(n)‏ تشخیص وجود دورمنفی در گراف 0۲60666550۲ : AQ

صفحه 50:
مقایسه دو روش الگوریتم ۱۵061-60۲۳61[۳9 ۸۵۱۱-۳۵۱۲5 از ماتریس برای اجرای الگوریتم. استفاده می کنند. مزایای این روش نسبت به ۵06۵/60 5۱0۲۲65۲ ۳۵۲۱ : سادگی و پیاده سازی لح دا ۴ معایب این روش : نیاز به حافظه زیاد‌عملکرد ض.ف و ها ۳ ‎(worst-case)‏ با وجود این معایب .این روش روش عمومی برای حل مساله کوتاه ترین مسیر بین زوج 4 50

جهت مطالعه ادامه متن، فایل را دریافت نمایید.
34,000 تومان