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

صفحه 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 

مساله کوتاه ترین مسیربین تمامی زوج راس ها زهرا عبدی ریحان منبع :بخش 5.6کتاب ‏Network Flows مساله کوتاه ترین مسیربین تمامی زوج راس ها ‏تعریف مساله ‏الگوریتم Shortest Path Repeated ‏الگوریتم All-Pairs Generic Label-correcting ‏مقایسه دوالگوریتم 2 تعریف مساله در مساله کوتاه ترین مسیر بین زوج راس ها ،فاصله کوتاه ترین مسیر بین هردو راس در شبکه تعیین می شود. راه حل ها: الگوریتم ،Shortest Path Repeatedاین الگوریتم برای شبکه های خلوت ( )Sparseمناسب است. الگوریتم ،All-Pairs Label-correctingاین الگوریتم برای شبکه های متراکم ( )denseمناسب است. 3 فرض مساله ‏شبکه ،قویاً همبند است. در شبکه قویاً همبند ،از هر گره به تمامی گره های دیگر یک مسیر جهت دار وجود دارد. به راحتی می توانیم این شرط را برقرار کنیم.با انتخاب یک راس دلخواه ( ،)sو افزودن یالهای ( )s, iو ( ) i , sبا هزینه های به اندازه کافی بزرگ به ازای راسهای }( iϵ N- {sدر صBBورBتBیکBBه یBBاBلمBربوطBه نBBباشد) ‏شبکه شامل دور منفی نیست. 4 الگوریتم Shortest Path Repeated حالت اول :شبکه شامل یال با طول منفی نیست. در این حالت با nباراجرای الگBوریتم Single Shortest Pathمی توانیم مساله را حل کنیم ( .هر بار یکی از گره ها را به عنوان منبع انتخاب میکنیم). حالت دوم :شبکه شامل یال هایی با طول منفی است. در این حالت ،ابتدا شبکه را به یک شبکه با طول های غیر منفی تبدیل می کنیم .سپس الگوریتم Single Shortest Pathرا برای هر کدام از رئوس اجرا می کنیم. 5 الگوریتم Shortest Path Repeated طریقه تبدیل شبکه به شبکه ای با طولهای غیرمنفی: ابتدا یک گره را به عنوان گره مبدا( )sانتخاب می کنیم .سپس الگوریتم FIFO Label Correctingرا اBجرا مBیکBBنی .م در اBیBنصBBورBتکBBم تBBریBنفBBاصBله از راBس sتBBا هBمه رBئوسدBیBگر مBحاسBبه مBیشBBود. با اجرای الگوریتم FIFO Label Correcting یا الگوریتم یک دور منفی را تشخیص می دهد .در این حالت مساله کوتاه ترین مسیر بین زوج راس ها جواب ندارد. یا برای همه رئوس کوتاهترین مسیراز راس sرا محاسبه می کند () .)d(jدر این حالت برای هر یال ،طول کاهش یافته را به صورت زیرمحاسبه می کنیم: 6 تبدیل شبکه به شبکه ای با طولهای غیرمنفی شبکه با طول کاهش یافته را تشکیل می دهیم .در این حالت: بنابراین شبکه به شبکه ای با طول های غیر منفی تبدیل شد. در شبکه کاهش یافته الگوریتم Single Shortest Pathرا برای nتا راس اجرا می کنیم. ‏درشبکه بدست آمده به مقدارکوتاه ترین فاصله بین دو راس lو kمقدار زیر را اضافه می کنیم تا مقدار واقعی کوتاه ترین فاصله در شبکه اولیه حاصل شود. 7 زمان اجرای الگوریتم ‏زمان تبدیل شبکه به شبکه با طول های غیر منفی : ‏FIFO Label Correcting : زمان اجرای الگوریتم )O(mn ‏زمان اجرای الگوریتم :Single Shortest Path )S(n,m,C ‏با nبا اجرای : Single Shortest Path ))O(n * S(n,m, C زمان اجرای الگوریتم : ))= O(m * n + n * S(n,m, C 8 )O(n* S(n,m,C قضیه الگوریتم repeated shortest pathکوتاه ترین مسیر بین زوج راس ها را در زمان ) O(n* S(n,m,Cحل می کند. 9 مثال 9 2 4 -2 4 -2 1 5 10 1 3 3 مثال 9 2 4 -2 4 -2 1 5 11 1 3 3 0 مثال   9 2 -2 0 4 4 -2 1 3 3 1 5   12 مثال ‏ ‏ 9 2 4 -2 4 -4 1 5 ‏ 13 1 3 3 3 0 مثال ‏ -2 9 2 4 -2 4 -2 1 5 ‏ 14 1 3 3 3 0 مثال 7 -2 9 2 4 -2 4 -2 1 5 ‏ 15 1 3 3 3 0 مثال 7 -2 9 2 4 -2 4 -2 1 5 5 16 1 3 3 3 0 مثال 7 -2 9 2 4 -2 4 -2 1 5 2 17 1 3 3 3 0 مثال 7 -2 9 2 4 -2 4 -2 1 5 2 18 1 3 3 3 0 مثال 7 -2 9 2 4 -2 4 -2 1 5 2 1 3 3 3 0 مثال 7 -2 9 2 4 -2 4 -2 1 5 2 20 1 3 3 3 0 مثال 0 7 9 4 3 -2 2 4 -2 0 -2 0 1 5 2 21 1 2 3 3 3 0 0 مثال بنابراین شبکه به شبکه ای با طول های غیر منفی تبدیل شد. فاصله راس 1و 0: 2 فاصله در شبکه اصلی : 2- =)2-(+ 0- 0 7 -2 0 2 4 0 0 فاصله راس 1و0 : 5 فاصله در شبکه اصلی : 2=0-0+2 3 5 2 22 1 0 3 2 3 0 الگوریتم All-Pairs Generic Label-correcting فرض کنید [ ]i , jنشانگر زوج راس iو jدر شبکه باشد. در الگوریتم ، All-Pairs Label-correctingمقدار ] d[i ,jنشان گر فاصله بین دو راس است. این برچسب ،طول گشت جهتدار از گره iبه گره jاست .و هم چنین حد باالی طول کوتاه ترین مسیر از راس iبه jاست. 23 شرایط بهینگی کوتاه ترین مسیر بین زوج راس ها قضیه :برای هر زوج راس های ] ،ϵ N*N [i ,jفرض کنید ] d[i ,jنشانگر طول یک مسیر جهتدار از راس iبه jباشد .این مقادیر ،فواصل کوتاه ترین مسیر بین زوج راس ها را نشان می دهد .اگر و تنها اگر شرط بهینگی زیر بر قرار باشد. ‏d[i, j]<= d[i,k] + d[k,j] for all nodes i, j and k 24 شرایط بهینگی کوتاه ترین مسیر بین زوج راس ها طرف اول :فرض می کنیم ماتریس 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 اثبات شرایط بهینگی یک گشت جهت دارمی تواند به یک مسیر جهت دار Pاز راس iبه jو چندین دور جهت دار تجزیه شود. ‏j ‏i ‏k 26 اثبات شرایط بهینگی یک گشت جهت دارمی تواند به یک مسیر جهت دار Pاز راس iبه jو چندین دور جهت دار تجزیه شود. ‏j ‏i ‏k مسیر جهت دار ‏P دور جهت دار 27 اثبات شرایط بهینگی چون دور با طول منفی نداریم بنابراین طول مسیر Pحداکثر ]d[i,k] + d[k,j است. طبق فرض داریم d[i, j] > d[i,k] + d[k,j] : ‏j در نتیجه طول مسیر Pحداکثر ] d[i, jاست. ‏i ‏k مسیر جهت دار ‏P دور جهت دار 28 اثبات شرایط بهینگی طول مسیر Pحداکثر ] d[i, jاست .که متناقض با فرض این که ] d[i, jکوتاهترین مسیر از راس iبه jاست. بنابراین ]d[i, j] <= d[i,k] + d[k,j ‏j ‏i ‏k مسیر جهت دار ‏P دور جهت دار 29 اثبات شرایط بهینگی طرف دوم: فرض می کنیم شرط زیر بر قرار باشد. ‏ 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 اثبات شرایط بهینگی می توانیم طبق فرض مساله بنویسم. می توانیم بنویسیم: بنابراین ] d[i,jیک کران پایین برای هر مسیر جهت دار از iبه jاست. 31 اثبات شرایط بهینگی d[i,j] یک کران پایین برای هر مسیر جهت دار از iبه jاست . از طرفی طبق فرض ] d[i ,jکران باالی کوتاهترین مسیر از iبه jاست. پس ] d[i ,jطول کوتاهترین مسیر از iبه jاست. 32 الگوریتم All-Pairs Generic Label-correcting در این الگوریتم مقدار ] d[i, jتا زمانی که شرط بهینگی برقرار شود به روز رسانی می شود. 33 اثبات درستی الگوریتم در هر مرحله از الگوریتم d[i , j] < است .شبکه شامل یک گشت جهت دار از گره iبه گره jاست. این گشت به یک مسیر جهت دار pو چندین دور جهت دار تجزیه شود. هیچ کدام از دور ها نمی توانند طول مثبت داشته باشند ( .در غیر این صورت بهینگی ] d[i , jبرقرار نمی شود ).پس دورها طول صفر دارند. در نتیجه مسیر Pطول ] d[i ,jدارد . .و شرط بهینگی مساله را هم دارد .و با اتمام الگوریتم مقادیر] d[i ,jطول کوتاهترین مسیرها را نشان می دهند. 34 اثبات fitnessبودن الگوریتم فرض می کنیم Cطول بزرگترین یال باشد .بیشترین مقداربرچسب فواصل n*C است .و کمترین مقدار – n*C الگوریتم تمام می شود. در هر تکرار مقدار ] d[i ,jکاهش می یابد .پس از است زمان اجرای الگوریتم 35 الگوریتم فلوید وارشال حالت خاصی از الگوریتم All-Pairs Generic Label- correcting است. از تکنیک برنامه نویسی پویا استفاده می کند. نشانگر طول کوتاه ترین مسیر از راس iبه راس jباشد که فقط فرض کنید از رئوس k-1… ,1,2,3,4,5به عنوان رئوس میانی استفاده می کند.در این صورت مقدار کوتاهترین مسیر نهایی از راس iبه راس jرا نشان می دهد. 36 الگوریتم فلوید وارشال این الگوریتم برای محاسبه مقدار یا از رئوس مرحله قبلی استفاه می کند و از راس kام عبور نمی کند : و یا حتماً از راس kام می گذرد: بنابراین مقدار 37 به صورت زیر محاسبه می شود. الگوریتم فلوید وارشال 38 مثال D(0) 3 2 7 1 4 1 3 8 2 -4 5 6 -5 4 0 3 8  -4  0  1 7  4 0   2  -5 0     6 0 39 مثال D(1) 3 2 7 1 4 1 3 8 2 -4 5 6 -5 4 0 3 8  -4  0  1 7  4 0   2 5 -5 0 -2    6 0 40 مثال D(2) 3 2 7 1 4 1 3 8 2 -4 5 6 -5 4 0 3 8 4 -4  0  1 7  4 0 5 1 1 2 5 -5 0 -2    6 0 41 مثال D(3) 3 2 7 1 4 1 3 8 2 -4 5 6 -5 4 0 3 8 4 -4  0  1 7  4 0 5 1 1 2 5 -5 0 -2    6 0 42 مثال D(4) 3 2 7 1 4 1 3 8 2 -4 5 6 -5 4 0 3 8 4 -4  0  1 7  4 0 5 1 1 2 5 -5 0 -2    6 0 43 مثال )D(5 -4 -1 3 -2 0 44 2 1 5 0 6 -1 -4 0 -5 1 3 0 4 -1 5 0 3 7 2 8 4 1 3 3 2 7 1 8 2 -5 4 -4 6 5 الگوریتم فلوید وارشال در این الگوریتم ] Pred[i ,jبرای هر زوج راس استفاده می شود .که شماره آخرین راس قبل از jرا نشان میدهد. پس از اتمام الگوریتم با استفاده از predرئوس و تکنیک عقب گرد می توانیم مسیر بین دو راس را پیدا کنیم. قضیه :الگوریتم فلوید وارشال کوتاه ترین مسیر بین زوج رئوس را در زمان حل می کند. 45 شناسایی دورهای منفی در الگوریتم 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 شناسایی دورهای منفی یک گشت بسته به تعدادی دور جهت دار تجزیه می شود. چون ، d[i,i] < 0بنابراین حداقل یکی از دورها ،باید منفی باشند. ‏i ‏k 47 شناسایی دورهای منفی حالت دوم d[i,j] < -n*C: در این حالت شبکه شامل یک گشت جهت دار از راس iبه راس jبا طول – n*Cاست. یک گشت جهتدار می تواند به یک مسیر جهت دارPو چندین دور جهتدار تجزیه شود. مسیر Pمی تواند حداقل طول ) -C*(n-1می تواند داشته باشد. بنابراین حداقل یکی از دورها باید دور منفی باشند. 48 شناسایی دورهای منفی در فلوید وارشال ‏ ‏ ‏ ‏ ‏ ‏ روش اول :در الگوریتم فلوید وارشال با چک کردن شرط < d[i,i] 0میتوانیم وجود دور منفی را تشخیص دهیم. می توانیم ثابت کنیم اگر دور منفی داشته باشیم همیشه d[i,i] < 0خواهد بود. روش دوم : می توانیم با استفاده از گراف predecessorوجود دور منفی را تشخیص دهیم. در صورتی که شبکه دور منفی نداشته باشد گراف predecessorیک درخت خواهد بود .ولی در حالتی که شبکه دور منفی داشته باشد گراف ، predecessorدور خواهد داشت. تشخیص وجود دورمنفی در گراف : predecessor 49 مقایسه دو روش الگوریتم All-Pairs Label-correctingاز ماتریس برای اجرای الگوریتم استفاده می کنند. مزایای این روش نسبت به : Path Shortest Repeatedسادگی و پیاده سازی راحت هست. معایب این روش :نیاز به حافظه زیاد،عملکرد ضعیف در حالت های بد ()worst-case با وجود این معایب ،این روش روش عمومی برای حل مساله کوتاه ترین مسیر بین زوج راس هاست. 50