مقدمه در نحوه حل مشکل کوتاهترین مسیر همه جفت را با استفاده از دیدیم. ما همچنین چندین راه را برای بهبود عملکرد الگوریتم با استفاده از موازی سازی و برداری بررسی کردیم. پست قبلی الگوریتم فلوید-وارشال با این حال، اگر به نتایج الگوریتم فلوید-وارشال فکر کنید، به سرعت لحظه جالبی را متوجه خواهید شد - ما فواصل (مقادیر کوتاه ترین مسیرها) بین راس ها را در یک نمودار می دانیم اما "مسیرها" را نمی دانیم، به عنوان مثال، ما نمی دانیم چه رئوس در کوتاه ترین مسیر کمک می کند، و نمی توانیم این "مسیرها" را از نتایجی که داریم بازسازی کنیم. در این پست از شما دعوت می کنم به من بپیوندید و الگوریتم فلوید-وارشال را گسترش دهید. این بار، ما میخواهیم مطمئن شویم که میتوانیم مسافت را محاسبه کرده و «مسیر» را بازسازی کنیم. کمی تئوری شناخته شده… قبل از پرداختن به کدها و معیارها، بیایید تئوری نحوه عملکرد الگوریتم فلوید-وارشال را بازبینی کنیم. در اینجا یک توضیح متنی از الگوریتم است: ما با نمایش یک نمودار ( ) به اندازه به عنوان ماتریس ( ) با اندازه شروع می کنیم که در آن هر سلول حاوی وزن یک یال از راس تا راس است (تصویر 1 را ببینید). در مواردی که هیچ لبه ای بین رئوس وجود ندارد، سلول روی یک مقدار ویژه تنظیم می شود (به عنوان سلول های تیره در تصویر 1 نشان داده شده است). G N W N x N W[i,j] i j NO_EDGE از این به بعد، می گوییم – حاوی فاصله بین رئوس و است. W[i,j] i j بعد، یک راس را می گیریم و در تمام جفت رئوس تکرار می کنیم و بررسی می کنیم که آیا فاصله از فاصله شناخته شده فعلی بین و کوچکتر است یا خیر. k W[i,j] i ⭢ k ⭢ j i j کوچکترین مقدار در ذخیره می شود و مرحله 3 برای بعدی تکرار می شود تا زمانی که تمام راس های به عنوان استفاده شوند. W[i,j] k G k این هم شبه کد: algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm پس از اتمام، هر سلول ماتریس یا حاوی فاصله کوتاهترین مسیر بین رئوس و یا مقدار است، اگر مسیری بین آنها وجود نداشته باشد. W[i,j] W i j NO_EDGE همانطور که در ابتدا اشاره کردم - داشتن تنها این اطلاعات باعث می شود که بازسازی مسیرهای بین این رئوس غیرممکن شود. پس... چه کار باید بکنیم تا بتوانیم این مسیرها را بازسازی کنیم؟ خوب… ممکن است واضح به نظر برسد اما… ما باید داده های بیشتری را جمع آوری کنیم! ... کمی از همان نظریه اما از زاویه ای متفاوت ماهیت الگوریتم فلوید-وارشال محفظه ای با فاصله شناخته شده با فاصله مسیر بالقوه جدید از تا از طریق راس میانی است. W[i,j] i j k من توجه زیادی را به این جزئیات جلب می کنم زیرا این کلید چگونگی حفظ اطلاعات مسیر است. بیایید نمودار قبلی 5 رأس را بگیریم (تصویر 2 را ببینید) و الگوریتم فلوید-وارشال را روی آن اجرا کنیم. در ابتدا، ما در مورد تمام یال های گراف می دانیم، که مسیرهای زیر را به ما می دهد: ، ، ، ، و . 0 ⭢ 1 :2 0 ⭢ 4 :10 1 ⭢ 3 :1 2 ⭢ 4 :1 3 ⭢ 2 :1 3 ⭢ 4 :3 من از قالب "از" ⭢ "به" :"فاصله" برای نوشتن مسیرها استفاده می کنم. پست قبلی - یادداشت نویسنده ما همچنین می دانیم که هیچ یال منتهی به راس وجود ندارد، بنابراین اجرای یک الگوریتم برای منطقی نیست. همچنین واضح است، یک یال منفرد ( ) وجود دارد که از راس به راس منتهی می شود، که همچنین اجرای همه ( "از اینجا" است) کاملاً بی معنی است و چون راس دارای یال هایی با و است، همچنین اجرای الگوریتم برای هر که یا نیست منطقی نیست ( در اینجا "to" است). 0 k = 0 0 ⭢ 1 0 1 i != 0 i 1 2 4 j 2 4 j به همین دلیل است که اولین قدم ما اجرای یک الگوریتم برای , و خواهد بود. k = 1 i = 0 j = 2,4 مرحله مسیر نظر دهید 1 0 ⭢ 1 ⭢ 2 مسیر پیدا شد فاصله = 3 (چیزی نبود) 2 0 ⭢ 1 ⭢ 4 مسیر پیدا شد فاصله = 8 (10 بود). ما دو مسیر پیدا کردهایم: یک مسیر جدید ( ) و یک میانبر ( ). هر دو از راس عبور می کنند. اگر این اطلاعات را (این حقیقت که به و تا رسیده ایم) در جایی ذخیره نکنیم، برای همیشه از بین می رود (و این کاملا برعکس چیزی است که ما می خواهیم). 0 ⭢ 1 ⭢ 2 0 ⭢ 1 ⭢ 4 1 2 4 1 پس باید چکار کنیم؟ ماتریس را با مقادیر جدید بهروزرسانی میکنیم (به تصویر 3a مراجعه کنید) و همچنین مقدار (که است) را در سلولهای و یک ماتریس جدید با همان اندازه ذخیره میکنیم. به عنوان ماتریس اما با مقادیر مقداردهی اولیه شده است (تصویر 3b را ببینید). W k k = 1 R[0,2] R[0,4] R W NO_EDGE در حال حاضر، روی اینکه دقیقاً ماتریس چیست تمرکز نکنید. بیایید ادامه دهیم و الگوریتم را برای بعدی اجرا کنیم. R k = 2 در اینجا، همان تجزیه و تحلیل را انجام خواهیم داد (برای اینکه بفهمیم اجرای چه ترکیبی منطقی است) همانطور که برای اما این بار، از ماتریس به جای نمودار استفاده خواهیم کرد. به ماتریس نگاه کنید، به خصوص در ستون #2 و ردیف #2 (تصویر 4). k = 1, W G W در اینجا می توانید ببینید، دو مسیر به راس از راس و از راس (ستون شماره 2) و دو مسیر از راس به راس و به راس (ردیف 2) وجود دارد. با دانستن این موضوع، اجرای الگوریتم فقط برای ترکیبات ، و منطقی است. 2 0 1 2 3 4 k = 2 i = 0,1 j = 3,4 مرحله مسیر نظر دهید 1 0 ⭢ 2 ⭢ 3 مسیر پیدا شد فاصله = 4 (چیزی نبود) 2 0 ⭢ 2 ⭢ 4 مسیر پیدا شد فاصله = 6 (8 شد) 3 1 ⭢ 2 ⭢ 3 مسیر پیدا شد فاصله = 2 (چیزی نبود) 4 1 ⭢ 2 ⭢ 4 مسیر پیدا شد فاصله = 4 (6 بود) همانطور که قبلاً انجام دادهایم، سلولهای , , , را با فواصل جدید و سلولهای بهروزرسانی میکنیم، ، و با (به تصویر 5 مراجعه کنید). W[0,3] W[0,4] W[1,3] W[1,4] R[0,3] R[0,4] R[1,3] R[1,4] k = 2 فقط برای پردازش باقی مانده است (زیرا هیچ لبه ای از راس به هر راس دیگری در نمودار وجود ندارد). k = 3 4 دوباره، بیایید نگاهی به ماتریس بیاندازیم (تصویر 6). W با توجه به ماتریس ، سه مسیر به راس از راس های ، و (ستون شماره 3) و یک مسیر از راس تا راس (ردیف 3) وجود دارد. بنابراین، ما مسیرهای زیر را برای پردازش داریم: W 3 0 1 2 3 4 مرحله مسیر نظر دهید 1 0 ⭢ 3 ⭢ 4 مسیر پیدا شد فاصله = 5 (6 بود) 2 1 ⭢ 3 ⭢ 4 مسیر پیدا شد فاصله = 3 (4 بود) 3 2 ⭢ 3 ⭢ 4 مسیر پیدا شد فاصله = 2 (3 بود) این آخرین تکرار الگوریتم بود. تنها چیزی که باقی میماند این است که سلولهای , , را با فواصل جدید بهروزرسانی کنید و سلولهای , , تا . W[0,4] W[1,4] W[2,4] R[0,4] R[1,4] R[2,4] 3 در اینجا چیزی است که ما در انتهای الگوریتم داریم (تصویر 7). همانطور که از می دانیم، ماتریس اکنون شامل تمام جفت ترین مسیرها در گراف است. اما چه چیزی در ماتریس ذخیره می شود؟ پست قبلی W G R بازگشت به خانه هر بار که کوتاه ترین مسیر جدید را پیدا می کردیم، سلول مربوطه ماتریس را با مقدار فعلی به روز می کردیم. در حالی که در ابتدا، این عمل ممکن است مرموز به نظر برسد، اما معنای بسیار سادهای دارد - ما راس را ذخیره میکردیم که از آنجا به راس مقصد رسیدیم: (در اینجا مستقیماً از به میرسیم). R k i ⭢ k ⭢ j k j این لحظه حیاتی است. زیرا دانستن رأسی که از آن آمدهایم به ما امکان میدهد با حرکت به عقب (مانند خرچنگ) از راس ("به") به راس ("از") مسیر را بازسازی کنیم. j i در اینجا یک توضیح متنی از الگوریتم برای بازسازی مسیر از به است: i j آرایه پویا خالی را آماده کنید. X با خواندن یک مقدار از سلول شروع کنید. z R[i,j] اگر باشد، مسیر تا پیدا می شود و باید به مرحله 7 برویم. z NO_EDGE i j به آرایه پویا اضافه کنید. z X مقدار سلول را به بخوانید. R[i,z] z مراحل #3، #4، و #5 را تا رسیدن به شرایط خروج در #3 تکرار کنید. به X اضافه کنید. i به اضافه کنید. j X اکنون آرایه پویا شامل مسیر تا است. X i j لطفا توجه داشته باشید، الگوریتم فوق فقط برای مسیرهای موجود کار می کند. همچنین از نقطه نظر عملکرد کامل نیست و مطمئناً می تواند بهینه شود. با این حال، در محدوده این پست، به طور خاص به گونه ای توضیح داده شده است که درک و تکثیر آن بر روی یک صفحه کاغذ آسان تر شود. - یادداشت نویسنده در شبه کد، حتی ساده تر به نظر می رسد: algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm بیایید آن را روی نمودار خود امتحان کنیم و مسیری از راس تا راس را دوباره بسازیم (تصویر 8 را ببینید). G 0 4 در اینجا شرح متنی تصویر بالا آمده است: ما با خواندن مقدار از شروع می کنیم که نتیجه آن است. طبق الگوریتم، این به این معنی است که مسیر از راس به راس می رود (نشان داده شده با رنگ آبی). R[0,4] 3 3 4 از آنجایی که مقدار نیست، ما ادامه می دهیم و مقدار را می خوانیم که به می رسد (نشان داده شده در سبز). R[0,4] NO_EDGE R[0,3] 2 باز هم، چون مقدار نیست، ادامه می دهیم و مقدار را می خوانیم که به می رسد (نشان داده شده در قرمز). R[0,3] NO_EDGE R[0,2] 1 در نهایت، مقدار را می خوانیم، که به مقدار منجر می شود، به این معنی که هیچ راس دیگری به جز و وجود ندارد که به مسیر کمک می کنند. بنابراین، مسیر به دست آمده عبارت است از: که اگر به نمودار نگاه کنید در واقع با کوتاه ترین مسیر از راس تا راس مطابقت دارد. R[0,1] NO_EDGE 0 4 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 0 4 یک خواننده متفکر ممکن است بپرسد: چگونه می توانیم مطمئن شویم که تمام داده هایی که از ماتریس می خوانیم به یک مسیر تعلق دارند؟ R - خواننده متفکر سوال بسیار خوبی است. ما مطمئن هستیم زیرا ماتریس با یک مقدار جدید بهروزرسانی میکنیم که کوتاهترین مقدار مسیر را در ماتریس بهروزرسانی کنیم. بنابراین در پایان، هر ردیف از ماتریس حاوی دادههای مربوط به کوتاهترین مسیرها است. نه بیشتر نه کمتر. R W R اکنون، ما با تئوری تمام شده ایم، زمان اجرا است. پیاده سازی در سی شارپ در ، علاوه بر پیادهسازی نسخه اصلی الگوریتم فلوید-وارشال، بهینهسازیهای مختلفی را نیز ادغام کردهایم: پشتیبانی از نمودارهای پراکنده، موازیسازی و بردارسازی، و در پایان، همه آنها را با هم ترکیب کردیم. پست قبلی هیچ دلیلی برای تکرار همه اینها امروز وجود ندارد. با این حال، من می خواهم به شما نشان دهم که چگونه حافظه مسیر را در نسخه های اصلی و برداری شده (با پشتیبانی از نمودارهای پراکنده) الگوریتم ادغام کنید. ادغام در الگوریتم اصلی شاید باورش سخت باشد اما برای ادغام حفظ مسیر در نسخه اصلی الگوریتم ها، تنها کاری که باید انجام دهیم این است: امضای تابع را گسترش دهید تا ماتریس را به عنوان یک پارامتر جداگانه در بر گیرد - . R int[] routes هر بار که کوتاهترین مسیر تغییر می کند k را در ذخیره کنید (خطوط 2 و 14). routes همین است. فقط یک و نیم خط کد: public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } } ادغام در الگوریتم برداری ادغام در یک نسخه برداری (با پشتیبانی از نمودارهای پراکنده) کمی تلاش بیشتری برای تکمیل نیاز دارد، با این حال، مراحل مفهومی یکسان هستند: امضای تابع را گسترش دهید تا ماتریس را به عنوان یک پارامتر جداگانه در بر گیرد - . R int[] routes در هر تکرار، یک بردار جدید از مقادیر را مقداردهی اولیه کنید (خط: 6). k هر بار که کوتاهترین مسیر تغییر می کند، بردار مقادیر را در ذخیره کنید (خطوط: 31-32). k routes یک بخش غیر برداری از الگوریتم را به همان روشی که الگوریتم اصلی را به روز کردیم (خط: 41) به روز کنید. public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } } یک یادآوری کوچک – عملیات یک بردار جدید را برمی گرداند که در آن مقادیر برابر با کوچکتر از دو مقدار متناظر بردارهای ورودی است، به عنوان مثال، اگر مقدار بردار برابر با باشد، این عملیات مقداری را از انتخاب می کند. در غیر این صورت، مقداری را از انتخاب می کند. Vector.ConditionalSelect lt_vec -1 ij_vec k_vec - یادداشت نویسنده محک زدن جمع آوری اطلاعات مسیر به اندازه کافی معقول به نظر می رسد زیرا... خوب چرا که نه؟ به خصوص زمانی که ادغام در الگوریتم های موجود بسیار آسان است. با این حال، بیایید ببینیم که ادغام آن به طور پیش فرض چقدر عملی است. در اینجا دو مجموعه از معیارها وجود دارد: با و بدون (هر دو نسخه اصلی و برداری الگوریتم را اجرا می کنند). همه بنچمارک ها توسط v0.13.1 (.NET 6.0.4 x64) بر روی دستگاهی مجهز به پردازنده Intel Core i5-6200U CPU 2.30GHz (Skylake) و دارای ویندوز 10 اجرا شدند. BenchmarkDotNet همه آزمایشها بر روی مجموعه از پیش تعریفشده نمودارهای مورد استفاده در انجام شد: رأسهای 300، 600، 1200، 2400 و 4800. پست قبلی کد منبع و نمودارهای آزمایشی در مخزن GitHub موجود است. نمودارهای آزمایشی را می توان در فهرست یافت. فایل پیاده سازی شده اند Data/Sparse-Graphs.zip تمامی بنچمارک های این پست در APSP02.cs . در زیر نتایج محک وجود دارد که روشهای و با نسخه اصلی الگوریتم و روشهای و با نسخه برداری (با پشتیبانی از نمودارهای پراکنده) الگوریتم مطابقت دارند. Baseline BaselineWithRoutes SpartialVectorOptimisations SpartialVectorOptimisationsWithRoutes روش اندازه میانگین (ms) خطا (ms) StdDev (ms) خط مبنا 300 40.233 0.0572 0.0477 BaselineWithRoutes 300 40.349 0.1284 0.1201 SpartialVector Optimisations 300 4.472 0.0168 0.0140 SpartialVector OptimisationsWithRoutes 300 4.517 0.0218 0.0193 خط مبنا 600 324.637 5.6161 4.6897 BaselineWithRoutes 600 321.173 1.4339 1.2711 SpartialVector Optimisations 600 32.133 0.2151 0.1679 SpartialVector OptimisationsWithRoutes 600 34.646 0.1286 0.1073 خط مبنا 1200 2,656.024 6.9640 5.8153 BaselineWithRoutes 1200 2,657.883 8.8814 7.4164 SpartialVector Optimisations 1200 361.435 2.5877 2.2940 SpartialVector OptimisationsWithRoutes 1200 381.625 3.6975 3.2777 خط مبنا 2400 21,059.519 38.2291 33.8891 BaselineWithRoutes 2400 20,954.852 56.4719 50.0609 SpartialVector Optimisations 2400 3,029.488 12.1528 11.3677 SpartialVector OptimisationsWithRoutes 2400 3,079.006 8.6125 7.1918 خط مبنا 4800 164,869.803 547.6675 427.5828 BaselineWithRoutes 4800 184,305. 980 210.9535 164.6986 SpartialVector Optimisations 4800 21882.379 200.2820 177.5448 SpartialVector OptimisationsWithRoutes 4800 21,004.612 79.8752 70.8073 تفسیر نتایج معیار ساده نیست. اگر نگاه دقیقتری بیندازید، ترکیبی را میبینید که در واقع جمعآوری مسیر باعث میشود الگوریتم سریعتر یا بدون تأثیر قابل توجهی اجرا شود. این بسیار گیج کننده به نظر می رسد (و اگر چنین است - من به شدت به شما توصیه می کنم که به این با و گوش دهید تا بهتر بفهمید چه چیزهای فریبنده ای می تواند بر اندازه گیری ها تأثیر بگذارد). بهترین برداشت من در اینجا این است که رفتار "گیج کننده" ناشی از عملکرد عالی حافظه نهان CPU است (زیرا نمودارها به اندازه کافی بزرگ نیستند که کش ها را اشباع کنند). تا حدی، این نظریه مبتنی بر نمونه " " است که در آن می توانیم تخریب قابل توجهی را در بزرگترین نمودار مشاهده کنیم. با این حال، من آن را تأیید نکردم. برنامه دنیس باخوالوف آندری آکینشین پررنگ به طور کلی، بنچمارک نشان میدهد که اگر در مورد سناریوهای بسیار با کارایی بالا و نمودارهای بزرگ صحبت نمیکنیم، خوب است که حافظه مسیر را به صورت پیشفرض در هر دو الگوریتم ادغام کنیم (اما به خاطر داشته باشید، مصرف حافظه را دوبرابر میکند، زیرا باید به جای یکی دو ماتریس و را اختصاص دهید). W R تنها چیزی که باقی می ماند اجرای الگوریتم بازسازی مسیر است. پیاده سازی الگوریتم بازسازی مسیر پیاده سازی الگوریتم های بازسازی مسیر در سی شارپ ساده است و تقریباً به طور کامل شبه کد نشان داده شده قبلی را منعکس می کند (ما برای نمایش آرایه پویا استفاده می کنیم): LinkedList<T> public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; } الگوریتم فوق کامل نیست و قطعاً قابل بهبود است. ساده ترین پیشرفتی که می توانیم انجام دهیم این است که یک آرایه با اندازه را از قبل تخصیص دهیم و آن را به ترتیب معکوس پر کنیم: sz public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); } در حالی که این "بهینه سازی" تعداد تخصیص ها را به یک کاهش می دهد، لزوما الگوریتم را "سریع تر" یا "تخصیص حافظه کمتر" نسبت به الگوریتم قبلی نمی کند. نکته اینجاست که اگر نیاز داشته باشیم مسیری مرتب شده از به داشته باشیم، همیشه باید دادههایی را که از ماتریس بازیابی میکنیم «معکوس» کنیم، و هیچ راهی برای فرار از آن وجود ندارد. i j R اما اگر بتوانیم دادهها را به ترتیب معکوس ارائه کنیم، میتوانیم از LINQ استفاده کنیم و از تخصیصهای غیرضروری اجتناب کنیم: public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; } میتواند انواع بیشتری از نحوه «تغییر» یا «بهبود» این کد وجود داشته باشد. لحظه مهم در اینجا این است که به یاد داشته باشید - هر "تغییر" از نظر حافظه یا چرخه های CPU دارای جنبه های منفی است. با خیال راحت آزمایش کنید! امکانات تقریبا نامحدود است! میتوانید پیادهسازی همه الگوریتمهای مسیر را در GitHub در فایل بیابید Routes.cs . نتیجه گیری در این پست، تئوری الگوریتم فلوید-وارشال را عمیقاً بررسی کردیم و آن را با امکان به خاطر سپردن مسیرهای کوتاهترین مسیرها گسترش دادیم. سپس پیادهسازیهای سی شارپ (اصلی و بردار) را از بهروزرسانی کردیم. در پایان، ما چند نسخه از الگوریتم را برای بازسازی "مسیرها" پیاده سازی کرده ایم. پست قبلی ما بسیار تکرار کرده ایم، اما در عین حال، امیدوارم چیز جدید و جالبی در این یکی پیدا کرده باشید. این پایان مشکل کوتاهترین مسیرهای همه جفت نیست. این تازه شروع کار است. امیدوارم از خواندن لذت برده باشید و دفعه بعد شما را ببینم!
