بلمن فورد¶

صورت مسئله¶

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

حال میخواهیم به ازای هر راس طول کوتاه ترین مسیر از راس \(sc\) به بقیه رئوس را پیدا کنیم که طول یک مسیر برابر جمع وزن های یال های آن است.

الگوریتم بلمن فورد¶

برای حل این مسئله ابتدا یک \(dp\) با ابعاد \(|V(G)| * |V(G)|\) تعریف میکنیم که \(dp_{i,j}\) برابر طول کوتاه ترین گشت از راس \(sc\) به راس \(j\) است که تعداد یال های این گشت حداکثر برابر \(i\) است.

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

حال برای پایه های این دپپی میدانیم که \(dp_{i, sc} = 0\) و \(dp_{0, u \neq sc} = \infty\) است. حال برای بدست اوردن \(dp_{i, j}\) روی تمامی یال هایی که به \(j\) وارد میشوند حالت بندی میکنیم. اگر به ازای هر یال \(e\) که از \(u_e\) به \(j\) وارد می شود و وزن آن \(w_e\) است، مقدار \(dp_{i-1, u_e} + w_e\) را حساب کنیم کمینه این مقدارها جواب \(dp_{i, j}\) می شود. در نتیجه :

برای بدست آوردن طول کوتاه ترین مسیر از راس \(sc\) به راس \(u\) داشتن مقدار \(dp_{n-1, u}\) کافی است. چون که مسیر از راس \(sc\) به یک راس دیگر حداکثر دارای \(n\) راس و \(n-1\) یال است و طبق تعریف دیپی و اینکه کوتاه ترین گشت بین 2 راس در \(G\) حتما مسیر است، این مقدار دقیقا همان مقدار مورد نیاز است.

تحلیل اردر¶

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

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

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

سپس \(|V(E)| - 1\) مرحله به ازای هر یال مقدار \(dp\) راس ته یال را اپدیت کرد. منظور از اپدیت کردن این است که اگر یال \(e\) از راس \(u_e\) به \(v_e\) برود و وزن آن \(w_e\) باشد، \(dp_{v_e} = min(dp_{v_e}, dp_{u_e} + w_e)\) را قرار دهیم.

حال یک سوال پیش می آید که آیا با انجام این کار مقدار خانه های \(dp\) همان مقدار مورد نظر باقی می ماند یا نه؟ پاسخ این سوال بله است.

اگر دیپی در قسمت قبلی را \(dp^{\prime}\) در نظر بگیریم بعد از مرحله \(i\) میدانیم \(dp_u\) برابر یکی از \(dp_{i, u}^{\prime}, dp_{i+1, u}^{\prime}, \dots, dp_{n-1, u}^{\prime}\) است. (اثبات این لم بر عهده خواننده).

حال اگر بعد از مرحله \(n-1\) مین بررسی کنیم میفهمیم که \(dp_u = dp_{n-1, u}^{\prime}\) است. در نتیجه بعد از مرحله \(n-1\) مین مرحله مقدار خانه های \(dp\) همان مقدار های مطلوب است.

پیدا کردن کوتاه ترین مسیر¶

بعد از همه این صحبت ها، یک سوال برایتان پیش می آید و آن این است که اگر خود مسیر بهینه از \(sc\) به یک راس دیگر مانند \(des\) را بخواهیم، چه باید بکنیم؟

برای حل این پرسش باید کمی الگوریتم قبلی را تغییر دهیم. یک آرایه \(|V(G)|\) عضوی کمکی به نام \(par\) در نظر میگیریم. در ابتدا تمامی خانه های \(par\) را برابر 1- قرار میدهیم. حال اگر در وقتی یال \(e\) را در نظر گرفتیم \(dp_{v_e} > dp_{u_e} + w_e\) بود، \(par_{v_e}\) را برابر \(u_v\) قرار میدهیم.

\(par_u\) عملا برابر راس قبلی در مسیر بهینه از \(sc\) به \(u\) است. برای بدست اوردن مسیر از \(sc\) به \(des\)، یک متغیر \(nw\) نگه میداریم و تا وقتی که \(nw \neq sc\) است، \(nw\) را برابر \(par_{nw}\) قرار میدهیم و \(nw\) را به ابتدا مسیر بدست امده فعلی اضافه میکنیم.

برای اثبات اینکه اثبات کنیم که حتما به راس \(sc\) میرسیم و مسیری که بدست می اوریم مسیری بهینه است، یک ارایه \(lst\) فرض میکنیم. \(lst_u\) برابر شماره اخرین مرحله ای است که \(dp_u\) عوض شده است. میدانیم \(lst_u > lst_{par_u}\) است. (اثبات به عهده خواننده) پس هر بار که \(nw\) را برابر \(par_{nw}\) می کنیم، \(lst_{nw}\) کاهش میابد پس به دور نمیخوریم و حتما به \(sc\) خواهیم رسید.

طول مسیر نیز برابر \(dp_{des}\) خواهد بود چون هر مرحله اگر یک یال با وزن \(w\) را به مسیر اضافه کنیم، مقدار \(dp_{nw}\) دقیقا به انداره \(w\) کاهش میابد. چون \(dp_{sc} = 0\) است طول مسیر دقیقا برابر \(dp_{des}\) میشود.

دور منفی¶

ممکن است برایتان سوال شود اگر تضمین نشود که گراف دور منفی دارد یا نه چگونه بفهمیم دور منفی داریم ؟ (در حالتی که حافظه را بهینه سازی کرده ایم).

ابتدا فرض کنید به جای \(|V(G)| - 1\) مرحله، \(|V(G)|\) مرحله اجرا میکنیم. به یک مرحله از الگوریتم خوب میگوییم اگر مقدار حداقل یکی از خانه های \(dp\) عوض شود. حال میدانیم اگر مرحله \(i\) م خوب نباشد آنگاه مراحل بعدی نیز خوب نیستند. (اگر مقداری عوض نشود مراحل بعدی هم دقیقا همانند مصل مرحله \(i\) م میشوند و خانه ای عوض نمیشود).

حال اگر دور منفی نداشته باشیم طبق استدلال های قبلی مرحله \(|V(G)|\) م حتما خوب نیست.(تمامی خانه ها به مقدار نهایی در مرحله قبل رسیده اند و عوض نخواهند شد). حال اگر یک دور منفی وجود داشته باشد میدانیم مقدار \(dp\) رِئوس آن هیچگاه ثابت نخواهد شد. خود دور منفی را میتوان چند بار طی کرد، که باعث میشود مقادیر \(dp\) رئوس دور به \(-\infty\) نزدیک شوند. حال میدانیم اگر یک مرحله خوب نباشد انگاه تمامی مقادیر ثابت شده اند. طبق این حرف ها نتیجه میشود اگر دور منفی داشته باشیم تمامی مراحل خوب خواهند بود.

حال میدانیم اگر دور منفی نداشته باشیم مرحله \(|V(G)|\) م خوب نیست و اگر دور منفی داشته باشیم \(|V(G)|\) م حتما خوب است. پس برای چک کردن داشتن دور منفی کافیست خوب بودن مرحله \(|V(G)|\) م را بررسی کنیم.

برای پیدا کردن خود دور منفی مثل حالت بدون دور منفی یک ارایه کمکی به نام \(par\) بگیرید و از یک راس که در مرحله \(|V(G)|\) م عوض شده مسیر بهینه از \(sc\) را پیدا کنید دور منفی در این مسیر حتما امده است. (این بخش با توجه به استدلال های همین بخش قابل اثبات است).