فلوید وارشال¶

صورت مسئله¶

یک گراف جهت دار وزن دار \(G\) داریم. وزن یال های \(G\) میتواند منفی نیز باشد. میدانیم گراف \(G\) دور با مجموع وزن منفی ندارد.

در این سوال به ازای هر جفت راس مانند \((u, v)\) طول کوتاه ترین مسیر از \(u\) به \(v\) را میخواهیم. طول یک مسیر برابر حمع وزن یال های آن است.

الگوریتم فلوید وارشال¶

برای حل این مسئله ابتدا یک \(dp\) با ابعاد \(|V(G)|.|V(G)|.|V(G)|\) تعریف میکنیم که \(dp_{k, i, j}\) برابر طول کوتاه ترین گشتی از راس \(i\) به راس \(j\) است که راس های وسطی آن (راس های مسیر به جز خود \(i\) و \(j\)) از بین مجموعه رئوس \(\lbrace 1, 2, \dots, k \rbrace\) است.

حال میدانیم طول کوتاه ترین گشت بین 2 راس در گراف \(G\) برابر طول کوتاه ترین مسیر نیز میباشد چون اگر کوتاه ترین گشت دارای 2 راس تکراری باشد یک دور داریم که طول آن مثبت است (طبق فرض سوال نمیتواند طول دور منفی باشد.) پس میتوان ان را حذف کرد و به یک گشت با طول کمتر رسید که تناقض است.

حال برای پایه های این دپپی میدانیم که \(dp_{0, i, i} = 0\) و به ازای هر جفت از رئوس مانند \((u, v)\) دیپی \(dp_{0, u, v}\) را برابر کوتاه ترین یال از \(u\) به \(v\) این دو راس میزاریم. ( اگر یالی از \(u\) به \(v\) نبود \(dp_{0, u, sc} = \infty\) است).

حال برای بدست اوردن \(dp_{k, i, j}\) دو حالت را در نظر میگیریم یا راس \(k\) در مسیر بهینه وجود ندارد که جواب در این حالت \(dp_{k - 1, i, j}\) است.

اگر راس \(k\) در مسیر باشد انگاه مسیر بهینه برابر \(dp_{k - 1, i, k} + dp_{k - 1, k, j}\) است چون که ابتدا از راس \(i\) باید به راس \(k\) برسیم و سپس از راس \(k\) به راس \(j\) برویم و در بین این دو مسیر حتما شماره رئوس از \(k\) کمتر است.

برای بدست آوردن طول کوتاه ترین مسیر از راس \(u\) به راس \(v\) داشتن مقدار \(dp_{n, u, v}\) کافی است.

تحلیل اردر¶

برای اپدیت کردن هر خانه دیپی \(\mathcal{O}(1)\) عملیات انجام داده ایم. میدانیم که دیپی دارای \(\mathcal{O}\left(\left|V\left(G\right)\right|^{3}\right)\) است. پس در کل \(\mathcal{O}\left(\left|V\left(G\right)\right|^{3}\right)\) عملیات انجام داده ایم. اردر حافظه استفاده شده نیز همان \(\mathcal{O}\left(\left|V\left(G\right)\right|^{3}\right)\) است.

بهینه سازی اردر حافظه¶

برای بهینه سازی مقدار حافظه مصرفی، میتوان بعد اول را حذف کرد. در نتیجه اردر حافظه مصرفی برابر \(\mathcal{O}\left(\left|V\left(G\right)\right|^{2}\right)\) میشود.

منظوز این است که یک \(for\) از 1 تا \(\left|V\left(G\right)\right|\) بزنیم و متغیر آن را \(k\) بنامیم. سپس در هر مرحله ازای هر خانه \(dp\) آن را اپدیت کنیم. منظور از اپدیت کردن این است که مثل حالت عادی روی اینکه راس \(k\) جزو راس های میانی مسیر هست یا نه حالت بندی کنیم.

حال برای اثبات درست بودن میگوییم که بعد هر مرحله حلقه اول تمامی مقادیر درست هستند. اگر ابتدا میگوییم که خانه های دیپی که یکی از بُعد های آن ها برابر \(k\) است هیچ گاه تغییری نمی کنند. حال برای آپدیت کردن بقیه خانه های دیپی از مقادیر خانه هایی استفاده میکنیم که حتما یک بُعد از انها \(k\) است.

پس با استقرا میتوان ثابت کرد که بعد مرحله \(k\) م \(dp_{i, j} = dp^{\prime}_{k, i, j}\) است که \(dp^{\prime}\) همان دیپی بدون بهینه سازی است. پس بعد مرحله :math:`n`م به مقادیر مطلوب خواهیم رسید.

پس با استقرا میتوان ثابت کرد که بعد مرحله \(k\) م \(dp_{i, j} = dp^{\prime}_{k, i, j}\) است که \(dp^{\prime}\) همان دیپی بدون بهینه سازی است. پس بعد مرحله \(n\) م به مقادیر مطلوب خواهیم رسید.

دور منفی¶

ممکن است برایتان سوال شود اگر تضمین نشود که گراف دور منفی دارد یا نه چگونه بفهمیم دور منفی داریم یا نه ؟ برای این هدف ابتدا \(dp_{i, i} = 0\) قرار میدهیم. حال اگر در حین اجرای الگوریتم یکی از خانه های \(dp_{i, i} < 0\) شد انگاه میدانیم یک گشت با طول منفی از \(i\) به \(i\) وجود دارد که میدانیم در هر گشت بسته با طول منفی دوری به طول منفی وجود دارد.

اگر دور منفی وجود داشت حتما برای راسی مانند \(u\) در دور منفی حتما \(dp_{u, u} < 0\) میشد. چون دور منفی ما طبق تعریف \(dp\) ما مشکلی ندارد و در \(dp_{u, u}\) تاثیر دارد و انرا منفی میکند.

طبق دو تا استدلال بالا وجود داشتن دور منفی با داشتن \(dp_{i, i} < 0\) معادل است. پس کافی است فقط بررسی کنیم در طول فرایند \(dp_{i, i}\) منفی نشود.