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

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

اسلاید 1: مساله کوتاه ترین مسیربین تمامی زوج راس هازهرا عبدی ریحانمنبع : بخش 5.6 کتابNetwork Flows

اسلاید 2: مساله کوتاه ترین مسیربین تمامی زوج راس هاتعریف مسالهالگوریتم Shortest Path Repeatedالگوریتم All-Pairs Generic Label-correctingمقایسه دوالگوریتم2

اسلاید 3: تعریف مساله در مساله کوتاه ترین مسیر بین زوج راس ها، فاصله کوتاه ترین مسیر بین هردو راس در شبکه تعیین می شود.راه حل ها: الگوریتم Shortest Path Repeated، این الگوریتم برای شبکه های خلوت (Sparse) مناسب است.الگوریتم All-Pairs Label-correcting، این الگوریتم برای شبکه های متراکم (dense) مناسب است. 3

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

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

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

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

اسلاید 8: زمان اجرای الگوریتمزمان تبدیل شبکه به شبکه با طول های غیر منفی : زمان اجرای الگوریتم 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

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

اسلاید 10: 213451934-2 مثال-210

اسلاید 11: 213451934-20 مثال -211

اسلاید 12: 213451934-20 مثال-212

اسلاید 13: 213451934-403 مثال -213

اسلاید 14: 1934-20-2312345 مثال -214

اسلاید 15: 1934-207-2312345 مثال-215

اسلاید 16: 1934-207-23512345 مثال -216

اسلاید 17: 1934-207-23212345 مثال -217

اسلاید 18: 1934-27-232012345 مثال-218

اسلاید 19: 1934-27-232012345 مثال -219

اسلاید 20: مثال213451934-27-2320-220

اسلاید 21: مثال213451934-27-2320000230-221

اسلاید 22: مثالبنابراین شبکه به شبکه ای با طول های غیر منفی تبدیل شد.فاصله راس 1و 2 :0 فاصله در شبکه اصلی : 0 -0 +(-2)= -2فاصله راس 1و5 : 0فاصله در شبکه اصلی :0-0+2=22134507-23200002322

اسلاید 23: الگوریتم All-Pairs Generic Label-correctingفرض کنید [i , j] نشانگر زوج راس iو j در شبکه باشد.در الگوریتم All-Pairs Label-correcting ، مقدار d[i ,j] نشان گر فاصله بین دو راس است.این برچسب، طول گشت جهتدار از گره i به گره j است. و هم چنین حد بالای طول کوتاه ترین مسیر از راس i به j است.23

اسلاید 24: شرایط بهینگی کوتاه ترین مسیر بین زوج راس هاقضیه : برای هر زوج راس های ϵ N*N [i ,j]، فرض کنید d[i ,j] نشانگر طول یک مسیر جهتدار از راس i به j باشد. این مقادیر ، فواصل کوتاه ترین مسیر بین زوج راس ها را نشان می دهد. اگر و تنها اگر شرط بهینگی زیر بر قرار باشد.d[i, j]<= d[i,k] + d[k,j] for all nodes i, j and k24

اسلاید 25: شرایط بهینگی کوتاه ترین مسیر بین زوج راس ها طرف اول : فرض می کنیم ماتریس D طول کوتاه ترین مسیر بین زوج راس ها باشد. در این صورت باید نشان دهیم :d[i, j]<= d[i,k] + d[k,j] for all nodes i, j and kاثبات : فرض می کنیم شرط حکم برقرار نباشد.d[i, j] > d[i,k] + d[k,j]در این صورت اجتماع کوتاه ترین مسیر جهتدار از راس i به k و k به j یک گشت جهت داربه طول d[i,k] + d[k,j] از راس i به j است.25

اسلاید 26: اثبات شرایط بهینگییک گشت جهت دارمی تواند به یک مسیر جهت دارP از راس i به j و چندین دور جهت دار تجزیه شود.ikj26

اسلاید 27: اثبات شرایط بهینگییک گشت جهت دارمی تواند به یک مسیر جهت دارP از راس i به j و چندین دور جهت دار تجزیه شود.ikj27مسیر جهت دار Pدور جهت دار

اسلاید 28: اثبات شرایط بهینگیچون دور با طول منفی نداریم بنابراین طول مسیر P حداکثر d[i,k] + d[k,j] است.طبق فرض داریم : d[i, j] > d[i,k] + d[k,j]در نتیجه طول مسیر P حداکثر d[i, j] است.ikj28مسیر جهت دار Pدور جهت دار

اسلاید 29: اثبات شرایط بهینگیطول مسیر P حداکثر d[i, j] است. که متناقض با فرض این که d[i, j] کوتاهترین مسیر از راس i به j است.بنابراین d[i, j] <= d[i,k] + d[k,j]ikj29مسیر جهت دار Pدور جهت دار

اسلاید 30: اثبات شرایط بهینگیطرف دوم:فرض می کنیم شرط زیر بر قرار باشد.d[i, j]<= d[i,k] + d[k,j] for all nodes i, j and kباید اثبات کنیم d[i ,j] طول کوتاهترین فاصله از مسیر i به j است.اثبات : فرض می کنیم P یک مسیر جهت دار به طول d[i,j] به صورت زیر باشد.30

اسلاید 31: اثبات شرایط بهینگی می توانیم طبق فرض مساله بنویسم.می توانیم بنویسیم: بنابراین d[i,j] یک کران پایین برای هر مسیر جهت دار از i به j است.31

اسلاید 32: اثبات شرایط بهینگی d[i,j] یک کران پایین برای هر مسیر جهت دار از i به j است . از طرفی طبق فرض d[i ,j] کران بالای کوتاهترین مسیر از i به j است.پس d[i ,j] طول کوتاهترین مسیر از i به j است.32

اسلاید 33: الگوریتم All-Pairs Generic Label-correctingدر این الگوریتم مقدار d[i, j] تا زمانی که شرط بهینگی برقرار شود به روز رسانی می شود.33

اسلاید 34: اثبات درستی الگوریتم در هر مرحله از الگوریتم d[i , j] <  است. شبکه شامل یک گشت جهت دار از گره i به گره j است.این گشت به یک مسیر جهت دارp و چندین دور جهت دار تجزیه شود. هیچ کدام از دور ها نمی توانند طول مثبت داشته باشند . (در غیر این صورت بهینگی d[i , j ] برقرار نمی شود.) پس دورها طول صفر دارند.در نتیجه مسیر P طول d[i ,j ] دارد. . و شرط بهینگی مساله را هم دارد. و با اتمام الگوریتم مقادیرd[i ,j] طول کوتاهترین مسیرها را نشان می دهند.34

اسلاید 35: اثباتfitness بودن الگوریتمفرض می کنیم C طول بزرگترین یال باشد . بیشترین مقداربرچسب فواصل n*C است. و کمترین مقدار n*C –در هر تکرار مقدار d[i ,j] کاهش می یابد. پس از الگوریتم تمام می شود.زمان اجرای الگوریتم است35

اسلاید 36: الگوریتم فلوید وارشالحالت خاصی از الگوریتم All-Pairs Generic Label- correcting است.از تکنیک برنامه نویسی پویا استفاده می کند. فرض کنید نشانگر طول کوتاه ترین مسیر از راس i به راس j باشد که فقط از رئوس 1,2,3,4,5, …k-1 به عنوان رئوس میانی استفاده می کند.در این صورت مقدار کوتاهترین مسیر نهایی از راس i به راس j را نشان می دهد.36

اسلاید 37: الگوریتم فلوید وارشال این الگوریتم برای محاسبه مقدار یا از رئوس مرحله قبلی استفاه می کند و از راس kام عبور نمی کند : و یا حتماً از راس k ام می گذرد: بنابراین مقدار به صورت زیر محاسبه می شود.37

اسلاید 38: الگوریتم فلوید وارشال 38

اسلاید 39: مثال 39D(0)2451334-4-567182038-4017402-5060

اسلاید 40: مثال 038-40174025-50-260D(1)2451334-4-56718240

اسلاید 41: مثال 0384-40174051125-50-260D(2)2451334-4-56718241

اسلاید 42: مثال 0384-40174051125-50-260D(3)2451334-4-56718242

اسلاید 43: مثال 0384-40174051125-50-260D(4)2451334-4-56718243

اسلاید 44: مثال 03-12-430-41-1740532-1-50-285160D(5)2451334-4-56718244

اسلاید 45: الگوریتم فلوید وارشالدر این الگوریتم Pred[i ,j] برای هر زوج راس استفاده می شود. که شماره آخرین راس قبل از j را نشان میدهد.پس از اتمام الگوریتم با استفاده از pred رئوس و تکنیک عقب گرد می توانیم مسیر بین دو راس را پیدا کنیم.قضیه : الگوریتم فلوید وارشال کوتاه ترین مسیر بین زوج رئوس را در زمان حل می کند.45

اسلاید 46: شناسایی دورهای منفیدر الگوریتم All-Pairs Label-correcting با چک کردن شروط زیر می توانیم وجود دور منفی را شناسایی کنیم. اثبات : حالت اول : d[i, i] < 0 می توانیم بنویسیم d[i, i] = d[i, k] + d[k,i] ، بنابراین شبکه شامل یک گشت جهتدار از i به k و یک گشت جهت دار دیگر از k به i است که مجموع طول این گشت ها d[i,i] است که عددی منفی است.اجتماع این دو گشت یک گشت بسته است.46

اسلاید 47: شناسایی دورهای منفییک گشت بسته به تعدادی دور جهت دار تجزیه می شود.چون d[i,i] < 0 ، بنابراین حداقل یکی از دورها، باید منفی باشند.ik47

اسلاید 48: شناسایی دورهای منفیحالت دوم :d[i,j] < -n*C در این حالت شبکه شامل یک گشت جهت دار از راس i به راس j با طول –n*C است. یک گشت جهتدار می تواند به یک مسیر جهت دارPو چندین دور جهتدار تجزیه شود. مسیر P می تواند حداقل طول C*(n-1)- می تواند داشته باشد. بنابراین حداقل یکی از دورها باید دور منفی باشند.48

اسلاید 49: شناسایی دورهای منفی در فلوید وارشالروش اول : در الگوریتم فلوید وارشال با چک کردن شرط < 0 d[i,i]میتوانیم وجود دور منفی را تشخیص دهیم.می توانیم ثابت کنیم اگر دور منفی داشته باشیم همیشه d[i,i] < 0 خواهد بود.روش دوم : می توانیم با استفاده از گراف predecessor وجود دور منفی را تشخیص دهیم.در صورتی که شبکه دور منفی نداشته باشد گراف predecessor یک درخت خواهد بود. ولی در حالتی که شبکه دور منفی داشته باشد گراف predecessor ، دور خواهد داشت.تشخیص وجود دورمنفی در گراف predecessor : 49

اسلاید 50: مقایسه دو روش الگوریتم All-Pairs Label-correcting از ماتریس برای اجرای الگوریتم استفاده می کنند. مزایای این روش نسبت به Path Shortest Repeated : سادگی و پیاده سازی راحت هست.معایب این روش : نیاز به حافظه زیاد،عملکرد ضعیف در حالت های بد (worst-case)با وجود این معایب ،این روش روش عمومی برای حل مساله کوتاه ترین مسیر بین زوج راس هاست.50