bellmanford

الگوریتم و کد Bellman-Ford برای کوتاه ترین مسیر از یک راس به سایر راس ها در گراف

bellmanford

یکی از الگوریتم هایی که برای پیدا کردن کوتاه ترین مسیر از یک راس ( راس سورس – source vertex ) به سایر راس ها در گراف استفاده می شود الگوریتم Bellman-Ford است. البته الگوریتم مشهور دیگری هم به اسم Dijkstra هست که احتمالا با آن آشنایی دارید ولی الگوریتم Dijkstra به هیچ وجه قابلیت گرفتن یک گراف با یال منفی را ندارد.  ولی Bellman-Ford قابلیت گرفتن گراف با یال های منفی را دارد.

در شکل زیر یک گراف جهت دار را می بینید که کوتاه ترین مسیر از راس ۰ به تمام راس ها در آن محاسبه شده و در گوشه ی سمت چپ پایین تصویر نوشته شده است(البته در تصویر پایین یک قسمتی نوشتم Adjacency List که اشتباه است و به آن توجه نکنید، در واقع‌ آن روشی است که گراف را از ورودی خوانده ام. این روش در سوال های مسابقه های برنامه نویسی رایج است. که فرمت ورودی را در آخر کد شرح داده ام) .

shortest-path-bellman-ford

اگر یک گراف دارای یال منفی باشد می تواند کوتاه ترین مسیر در آن از یک راس به سایر راس ها وجود داشته باشد ولی اگر در گراف دوری داشته باشیم که مجموع جمع وزن یال های آن منفی باشد کوتاه ترین مسیر از یک راس به سایر راس ها وجود ندارد چون می توانیم بی نهایت بار روی دور حرکت کنیم و هزینه ی مسیر را کم تر کنیم. مانند تصویر زیر که در آن حلقه ای منفی وجود دارد:

negative-cycle

ولی اگر آن یال منفی هشت را با منفی سه جایگزین کنیم مشکلی پیش نمی آید چون دور منفی نداریم. در تصویر زیر کوتاه ترین مسیر ها را می بینید:

shortest-path-bellman-ford-with-negative-edge

قبل از اینکه بریم سراغ الگوریتم Bellman-Ford تابع Relax را شرح می دهیم. این تابع فاصله سورس تا دو راس ابتدا و انتهای یک یال جهت دار می گیرد و همین طور وزن یال را و سپس فاصله ی سورس تا راس انتهای یال را به صورت زیر آپدیت می کند.

در الگوریتم Bellman-Ford برای هر راس دو ویژگی در نظر می گیریم یکی distance که فاصله ی  راس  سورس تا آن راس است و در آخر کار قرار است کوتاه ترین فاصله از راس سورس تا آن راس در آن قرار داشته باشد. و دومین ویژگی parent است که مشخص می کند پدر یک راس کدام راس است در تصویر بالا کوتاه ترین مسیر بین ۰ و ۱ برابر  ۱ ۲ ۳ ۰ است یعنی برای اینکه از ۰ به یک ۱ آمده باشیم باید قبل از آن به ۲ برویم یعنی پدر یک برابر دو است و قبل از اینکه از ۰ به ۲ برویم باید به ۳ برویم یعنی پدر ۲ برابر سه است.

به تصویر زیر توجه کنید که دو راس u و v در آن وجود دارد و یالی با وزن ۵ از راس u خارج می شود و به v وارد می شود. فرض کنید که ما قبلا یک مسیری از راس سورس (source) تا v پیدا کرده ایم و طول آن ۱۳ است و همین طور یک مسیر دیگر از سورس تا راس u پیدا کرده ایم و طول آن ۳ است. تابع relax می بیند، فاصله مسیری که قبلا  از راس سورس تا v رفته ایم آیا از مسیری که از سورس تا u رفته ایم به علاوه ی وزن یالی که از u خارج و به v وارد می شود، کمتر است یا نه ! اگر فاصله ی سورس تا u به علاوه ی وزن یال u به سمت v کمتر از فاصله سورس تا v باشد به این معنی است که مسیری کوتاه تر از سورس به v از طریق u پیدا کرده ایم که از مسیر قبلی سورس تا v کوتاه تر است. در نتیجه فاصله ی سورس تا v را آپدیت می کنیم و پدر v را برابر با u می کنیم. و اگر هم فاصله ی سورس تا u به علاوه ی وزن یال بیشتر از فاصله ی سورس تا v بود چیزی را آپدیت نمی کنیم زیرا همان مسیر قبلی تا از سورس تا v کوتاه تر از مسیر راس سورس تا u به علاوه ی یالی که از u خارج می شود و به v وارد می شود است.

relax

در زیر کد تابع relax را می بینید :

آرگومان های تابع relax:

distance : یک وکتور است به تعداد راس های گراف که خانه ی i ام آن فاصله ی سورس تا راس i  ام است.

parent : یک وکتور به طول تعداد راس های گراف است که خانه ی i ام آن پدر راس i است.

startOfEdge: راس آغازین یال است.

endOfEdge: راسی است که یال به آن منتهی می شود.

weightofEdge : وزن یال است. از آنجایی که ممکن است وزن یال ها را بخواهید اعشاری تعریف کنید نوع وزن یال ها Template تعریف شده است.

 

بعد از تابع relax به سراغ تابع  initial single source می رویم. این تابع فاصله ی تمام سورس تا تمام راس ها را برابر بی نهایت (یک مقدار بزرگ) قرار می دهد. و فاصله سورس تا خود سورس را برابر صفر می کند. و همین طور پدر همه ی راس ها را برابر ۱- می گذارد. یعنی ابتدا هیچ راسی پدرش مشخص نشده است. در زیر کد تابع relax را می بینیم:

آرگومان ها:

source : راسی است که می خواهیم کوتاه ترین مسیر از آن راس به سایر راس ها را به دست بیاریم.

قبل از اینکه به سراغ الگوریتم Bellman-Ford برویم نشان بدهیم که با چه ساختمان داده ای گراف خود را نگاه می داریم. برای نگهداری گراف و راس ها و یال ها از

استفاده می کنیم. راه های مختلفی برای نگه داری گراف است یکی از آن ها ماتریس مجاورت است و یکی دیگر از آن ها لیست مجاورت است، این دو روش رایج ترین روش ها برای نگه داری گراف هستند. adjList یک لیست مجاورت است. adjList یک وکتور(vector) از وکتور ها است که هر وکتور درون آن یک pair است. adj List یک وکتور از وکتور ها است که خانه ی i ام آن شامل یک وکتور است که یال های خارج شده از راس i را نگه می دارد.

خانه ی i ام وکتور بیرونی شامل یک وکتور است که pair هایی را نگه می دارد. هر کدام از این pair ها نشان دهنده ی یک یال است. هر pair دو قسمت دارد قسمت اول( first ) و دوم ( second ). قسمت اول pair در اینجا راسی را نشان می دهد که یالی که از خانه ی i ام خارج شده به آن وارد شده است و قسمت دوم pair نشان دهنده ی وزن یال است. این روش نگه داری گراف بسیار مرسوم است و در الگوریتم های بعدی هم احتمالا از این روش استفاده کنیم. در صورتی که متوجه نشدید می توانید به تصویر زیر دقت کنید:

ajacency-list

 

خوب حالا برویم سراغ خود الگوریتم bellman-ford برای محاسبه ی کوتاه ترین مسیر از یک راس به سایر راس ها. در یک گراف که n راس دارد هر مسیر ساده ای  از یک راس تا یک  راس دیگر در صورتی یک راس را بیش از یک بار نبینیم حداکثر  n – 1 یال وجود دارد. یک مسیر بین دو راس می تواند شامل هیچ راسی دیگری نباشد در این صورت هر دو راس به صورت مستقیم به هم وصل شده اند. یا بین دو راس n – 2 راس دیگر وجود داشته باشد در این صورت در مسیر n – 1 یال داریم.

فرض کنید یک گراف را با استفاده از تابع initial single source مقدار دهی اولیه کرده ایم. بعد از این کار فاصله ی همه راس ها تا راس سورس برابر بینهایت (یک مقدار بزرگ) است بجز خود سورس که فاصله اش با خودش برابر صفر است. در ابتدا برای تمام یال های گراف تابع relax را فرا می خوانیم. خوب چه اتفاقی می افتد بعد از فراخوانی تابع ریلکس برای تمام یال ها‌؟ راس هایی که مستقیم به سورس هستند فاصله شان تا سورس آپدیت می شود و مقدارشان از بی نهایت به یک مقدار مشخص تغییر پیدا می کند. سایر راس ها چطور؟ بستگی به ترتیب ریلکس کردن یال ها دارد ممکن است مقدارشان آپدیت شود و یا همان بینهایت بماند. فرض کنید یک یال را ریلکس می کنیم بطوری که یال های متصل به آن قبل از آن ریلکس نشده است در نتیجه در سر آغازین یال مقدار بی نهایت است و سر پایانی آن هم بی نهایت می ماند. و از آن طرف هم مقدار فاصله ی بعضی از راس ها آپدیت می شود ولی این دلیل بر آن نیست که مقدار آپدیت شده فاصله سورس تا آن راس کوتاه ترین مسیر باشد. چون ممکن است کوتاه ترین مسیر بین راس تا یک نود شامل یک راس باشد و  بار اول relax کردن تمام یال ها فقط زمانی معتبر است که کوتاه ترین مسیر از سورس تا یک راس شامل هیچ راس دیگری نباشد و دو راس مستقیم به هم وصل شده باشند. به همین دلیل برای بار دوم تمام یال ها را relax می کنیم. بعد از این کار ممکن است بعضی از راس ها آپدیت شوند و بعضی ها نشوند. در این مرحله در صورتی که کوتاه ترین فاصله ی از راس سورس تا یک راس شامل دو یال (یک راس در میان دو راس) باشد دیگر با relax کردن های بیشتر مقدار آن تغییر نمی کند. ولی برای بعضی ها مقدار distance قابل قبول نیست زیرا ممکن است کوتاه ترین مسیر از راس سورس تا یک راس شامل سه یال (دو راس در وسط) باشد در این صورت باید یک بار دیگر تمام یال ها را relax کنیم. از آنجایی که در گرافی که n راس دارد حداکثر یک مسیر می تواند شامل n – 1 یال باشد باید n – 1 بار تمام یال ها را relax کنیم . و این همان کاری است که الگوریتم Bellman-Ford می کند. در زیر تصویری از این روش را می بینید که ۴ بار تمام یال ها ریلکس شده اند و هر بار تغییرات با رنگ پررنگ مشخص شده است.

bellman-ford-clrs-pic    وقت نشد ببینم لایسنس کپی رایت کتاب سی ال آر اس چیه به همین خاطر اسم کتاب تو تصویر گذاشتم. بعدا چک می کنم اگر مشکل داشت خودم تصویرش می سازم می ذارم.

در زیر کد الگوریتم Bellman-Ford را که با سی پلاس پلاس نوشته شده است را می بینید:

که همه ی آرگمان های ورودی آن را در بالا شرح داده ایم. خروجی این تابع یک مقدار bool است که اگر true باشد نشان می دهد دوری در گراف که مجموع یال های آن منفی شود نداریم و مقدار distance و parent معتبر است. ولی اگر false باشد یعنی دوری داریم که مجموع یال های روی آن منفی است در نتیجه آن گراف کوتاه ترین مسیر ندارد و مقادیر distance و parent نامعتبر است.

چگونه تشخص دهیم دوری داریم که مجموع یال های آن منفی است؟ این کار بسیار ساده است. اگر بعد از n – 1 بار relax کردن تمام یال ها بتوانیم یالی را پیدا کنیم که بعد از ریلکس کردن آن یال فاصله ی سورس تا سر یال آپدیت شود آنگاه می توان گفت که دور با مجموع منفی در گراف داریم همان دو for تو در توی پایانی کد بالا این کار را می کند.

در کد سی پلاس پلاس  (++C) زیر کد کلی الگوریتم کوتاه ترین مسیر bellman ford را می بینید به همراه یک تابع main که در تابع main ماتریس از ورودی گرفته شده است و کوتاه ترین مسیر از راس ۰ به سایر راس ها حساب شده است و مسیر و فاصیله برای آن ها چاپ شده است. در پایان کد هم یک سری ورودی داده شده است که به صورت کامنت شده هستند که می توانید آن ها را جهت تست کد استفاده کنید. فرمت ورودی گراف هم در پایان کد در قسمت کامنت شده آورده شده است. که با خواندن کد هم آن را متوجه می شوید.

در زیر یک نمونه از اجرای برنامه را می بینید:

screenshot-from-2016-12-26-02-22-35

هزینه ی الگوریتم:

bellman ford در مجموع به تعداد راس ها (V) منهای یک عمل relax کردن تمام یال ها را انجام می دهد و در هر بار به تعداد تمام یال ها (E) عمل ریلکس کردن را انجام می دهند که درنتیجه هزینه ی کلی الگوریتم برابر با Θ(V.E) می شود.

در پست بعدی در مورد Dijkstra صحبت می کنیم.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *