آبجی
21st February 2010, 01:15 PM
الگوریتم بلمن-فورد الگوریتم پیمایش گراف است که مسئلهٔ کوتاهترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که وزن یال‌ها ممکن استن منفی باشد حل می‌کند.
الگوریتم دَیکسترا مسئلهٔ مشابهی را در زمان اجرای کمتر حل می‌کند، اما در آن الگوریتم می‌بایست وزن یال‌ها اعداد نامنفی باشند. بنابراین در عمل الگوریتم بلمن-فورد فقط برای گراف‌هایی که یال با وزن منفی دارند استفاده می‌شود.
قبل از توضیح الگوریتم لازم به ذکر است که اگر گراف دوری با مجموع وزن منفی داشته باشد که از مبدأ قابل دست‌یابی باشد، مسئلهٔ کوتاهترین مسیر جوابی نخواهد داشت، چراکه با پیمایش آن دور به هر تعداد بار دلخواه، مسیرهایی با وزن کمتر و کمتر حاصل خواهد شد.
چگونه کار می‌کند؟
ساختار اصلی الگوریتم بلمن-فورد مشابه الگوریتم دایجکسترا است. اجرای الگوریتم 1-|V| دنبالهٔ d چنان تعریف می‌شود که برای هر رأس v، مقدار dv در پایان مرحلهٔ iام برابر وزن کوتاهترین گذر از مبدأ به v است با این شرط اضافه که تعداد یال‌های این گذر حداکثر i باشد. بنابراین در پایان مرحلهٔ (1-|V|)ام dv برابر وزن کوتاهترین مسیر از مبدأ به v خواهد بود (در واقع چون دور با مجموع وزن منفی نداریم، کوتاهترین گذر با حداکثر 1-|V| یال از مبدأ به v، همان کوتاهترین مسیر از مبدأ به v در گراف خواهد بود).
اساس کار الگوریتم آزادسازی (Relaxation) همهٔ یال‌های گراف در هر مرحله‌است. آزادسازی یال (u,v) به این معناست که اگر du + weight(u,v) < dv آنگاه قرار می‌دهیم du + weight(u,v) = dv. با این اوصاف اگر آزادسازی همهٔ یال‌ها را برای بار |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 dw = http://upload.wikimedia.org/math/d/2/4/d245777abca64ece2d5d7ca0d19fddb6.png
8 ds = 0
9 for i = 1 to |V|-1 do
10 for all edge (u,v) in E do
11 if du + weight(u,v) < dv then
12 dv = du + weight(u,v)
13 for all edge (u,v) in E do
14 if du + weight(u,v) < dv then
15 return False
16 return True
17 end
پیچیدگی زمانی
مشخص است که در 1-|V| مرحله، در هر مرحله |E| عملیات بر روی یال‌ها انجام می‌شود. پس پیچیدگی زمانی الگوریتم بلمن-فورد (|O(|V|×|E است.
منبع:ويكيپديا
الگوریتم دَیکسترا مسئلهٔ مشابهی را در زمان اجرای کمتر حل می‌کند، اما در آن الگوریتم می‌بایست وزن یال‌ها اعداد نامنفی باشند. بنابراین در عمل الگوریتم بلمن-فورد فقط برای گراف‌هایی که یال با وزن منفی دارند استفاده می‌شود.
قبل از توضیح الگوریتم لازم به ذکر است که اگر گراف دوری با مجموع وزن منفی داشته باشد که از مبدأ قابل دست‌یابی باشد، مسئلهٔ کوتاهترین مسیر جوابی نخواهد داشت، چراکه با پیمایش آن دور به هر تعداد بار دلخواه، مسیرهایی با وزن کمتر و کمتر حاصل خواهد شد.
چگونه کار می‌کند؟
ساختار اصلی الگوریتم بلمن-فورد مشابه الگوریتم دایجکسترا است. اجرای الگوریتم 1-|V| دنبالهٔ d چنان تعریف می‌شود که برای هر رأس v، مقدار dv در پایان مرحلهٔ iام برابر وزن کوتاهترین گذر از مبدأ به v است با این شرط اضافه که تعداد یال‌های این گذر حداکثر i باشد. بنابراین در پایان مرحلهٔ (1-|V|)ام dv برابر وزن کوتاهترین مسیر از مبدأ به v خواهد بود (در واقع چون دور با مجموع وزن منفی نداریم، کوتاهترین گذر با حداکثر 1-|V| یال از مبدأ به v، همان کوتاهترین مسیر از مبدأ به v در گراف خواهد بود).
اساس کار الگوریتم آزادسازی (Relaxation) همهٔ یال‌های گراف در هر مرحله‌است. آزادسازی یال (u,v) به این معناست که اگر du + weight(u,v) < dv آنگاه قرار می‌دهیم du + weight(u,v) = dv. با این اوصاف اگر آزادسازی همهٔ یال‌ها را برای بار |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 dw = http://upload.wikimedia.org/math/d/2/4/d245777abca64ece2d5d7ca0d19fddb6.png
8 ds = 0
9 for i = 1 to |V|-1 do
10 for all edge (u,v) in E do
11 if du + weight(u,v) < dv then
12 dv = du + weight(u,v)
13 for all edge (u,v) in E do
14 if du + weight(u,v) < dv then
15 return False
16 return True
17 end
پیچیدگی زمانی
مشخص است که در 1-|V| مرحله، در هر مرحله |E| عملیات بر روی یال‌ها انجام می‌شود. پس پیچیدگی زمانی الگوریتم بلمن-فورد (|O(|V|×|E است.
منبع:ويكيپديا