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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم بلمن-فورد الگوریتم پیمایش گراف است که مسئلهٔ کوتاهترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که وزن یال‌ها ممکن است منفی باشد حل می‌کند.

الگوریتم دَیکسترا مسئلهٔ مشابهی را در زمان اجرای کمتر حل می‌کند، اما در آن الگوریتم می‌بایست وزن یال‌ها اعداد نامنفی باشند. بنابراین در عمل الگوریتم بلمن-فورد فقط برای گراف‌هایی که یال با وزن منفی دارند استفاده می‌شود.

قبل از توضیح الگوریتم لازم به ذکر است که اگر گراف دوری با مجموع وزن منفی داشته باشد که از مبدأ قابل دست‌یابی باشد، مسئلهٔ کوتاهترین مسیر جوابی نخواهد داشت، چراکه با پیمایش آن دور به هر تعداد بار دلخواه، مسیرهایی با وزن کمتر و کمتر حاصل خواهد شد.

چگونه کار می‌کند؟[ویرایش]

ساختار اصلی الگوریتم بلمن-فورد مشابه الگوریتم دایکسترا است. اجرای الگوریتم 1-|V| دنبالهٔ d چنان تعریف می‌شود که برای هر رأس v، مقدار d_v در پایان مرحلهٔ iام برابر وزن کوتاهترین گذر از مبدأ به v است با این شرط اضافه که تعداد یال‌های این گذر حداکثر i باشد. بنابراین در پایان مرحلهٔ (1-|V|)ام d_v برابر وزن کوتاهترین مسیر از مبدأ به v خواهد بود (در واقع چون دور با مجموع وزن منفی نداریم، کوتاهترین گذر با حداکثر 1-|V| یال از مبدأ به v، همان کوتاهترین مسیر از مبدأ به v در گراف خواهد بود).

اساس کار الگوریتم آزادسازی (Relaxation) همهٔ یال‌های گراف در هر مرحله‌است. آزادسازی یال (u,v) به این معناست که اگر d_u + weight(u,v) <d_v آنگاه قرار می‌دهیم d_v = d_u + weight(u,v). با این اوصاف اگر آزادسازی همهٔ یال‌ها را برای بار |V|ام هم تکرار کنیم و بعد از این مرحله هم دنبالهٔ d تغییر کند، آنگاه می‌توان نتیجه گرفت که گراف دور منفی‌ای دارد که از مبدأ قابل دست‌یابی است. بنابراین الگوریتم بلمن-فورد توانایی تشخیص دور منفی را نیز دارد.

الگوریتم[ویرایش]

همانطور که گفته شد الگوریتم بلمن-فورد توانایی تشخیص دور منفی را نیز دارد. بنابر این الگوریتم را به گونه‌ای پیاده‌سازی می‌کنند که در صورت تشخیص دور منفی مثلاً مقدار بولی True برگرداند.

پیاده‌سازی[ویرایش]

یک پیاده‌سازی نوعی به این شرح است:

 1  Algorithm Bellman-Ford(G,s)
 2  Input : G=(V,E), s(the source vertex)
 3  Output : Sequence d and a boolean return value
 4  begin
 5      for all vertices w do
 6          d_w  = \infty 
 8      d_s  = 0
 9      for i = 1 to |V|-1 do
10          for all edge (u,v) in E do
11              if d_u + weight(u,v) <d_v  then
12                  d_v = d_u + weight(u,v)
13      for all edge (u,v) in E do
14          if d_u + weight(u,v) <d_v  then
15              return False
16      return True
17  end

اثبات درستی[ویرایش]

می توان درستی را با استفاده از استقرای ریاضی نشان داد.

لم. بعد از i بار تکرار حلقه:

  • اگر Distance(u) بی نهایت نباشد، برابر است با فاصله ی مسیری از s به u.
  • اگر مسیری از s به u با حداکثر i شاخه وجود داشته باشد، بنابرین Distance(u) حداکثر دارای طول کوتاه ترین مسیر با طول i خواهد بود.

اثبات. ابتدا حالت پایه استقرا را در نظر بگیریم که در آن i=0. در این حالت source.distance = 0 که درست است. به ازای تمامی گره های غیر از منباu داریم u.distance = infinity که درست است؛ چون که هیچ مسیری از منبا به این گره ها با طول مسیر صفر وجود ندارد.

ابتدا قسمت اول را اثبات می کنیم. با فرض استقرا فرض کنیم u.distance طول مسیری از منبا به u باشد. در اینصورت u.distance + uv.weight طول مسیری از منبا به v است.

برای قسمت دوم، فرض کنیم طول کوتاه ترین مسیر از منبا به u حداکثر i باشد. فرض کنیم v گرهی قبل از u در طول این مسیر باشد، در اینصورت طول کوتاه ترین مسیر به v برابر با i-1 است. بنابه فرض استقرا بعد از i-1 تکرار حلقه، کوتاه ترین مسیر تا v با طول i-1 پیدا شده است. در اینصورت چون در i-امین تکرار حلقه uv.weight + v.distance با u.distance مقایسه می شود حتماً کوتاه ترین مسیر با طول i در i امین تکرار پیدا خواهد شد.

توجه کنید که در چنین درختی که مسیر شامل حلقه نداریم، حداکثر طول مسیر بابر با |V|-1 است. لذا الگوریتم مورد نظر بعد از اتمام جواب بهینه را بدست خواهد داد.

پیچیدگی زمانی[ویرایش]

مشخص است که در 1-|V| مرحله، در هر مرحله |E| عملیات بر روی یال‌ها انجام می‌شود. پس (|O(|V|×|E پیچیدگی زمانی الگوریتم بلمن-فورد خواهد بود.

کاربردها[ویرایش]

پیوند به بیرون[ویرایش]

منابع[ویرایش]