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

الگوریتم بل من فورد کوتاهترین مسیر را در یک گراف وزن دار محاسبه می‌کند، برای گراف‌هایی با یال‌های با وزن غیر منفی، الگوریتم سریعتر دایجکسترا نیز آن را حل کرده‌است، بل من فورد ابتدا برای گراف‌هایی با یال‌های منفی استفاده می‌شد.الگوریتم به نام سازندگان آن یعنی ریچارد بل من و لستر فورد نام‌گذاری شده‌است.
اگر گراف دارای یک دور منفی مثل یک حلقه که مجموع یالها به یک مقدار منفی میل می‌کند باشد، یک پیمایش کم وزن دلخواهانه می‌تواند ساخته شود که مثلا آن می‌تواند کوتاهترین مسیر باشد.
بل من فورد می‌تواند حلقه‌های منفی را شناسایی ووجود آن‌ها را گزارش دهد ولی اگر یک دور منفی از مبدا قابل دسترسی باشد نمی‌تواند یک جواب صحیحی را بسازد.
با توجه به سخنان رابرت سجویک وزن‌های منفی منحصرا یه چیز غریب محاسباتی نیستند.آنها در یک مسیر طبیعی رخ می‌دهند وقتی که ما بقیه مشکلات را برای مشکلات و مسائل کوتاهترین مسیرکاهش می‌دهیم.
گیریم G یک گراف که شامل دور منفی باشد.یک NP Compelet متفاوت مسئله کوتاهترین مسیر، دنبال کوتاهترین راه در G ( شامل یک دور منفی ) است، به‌طوری‌که هیچ یالی تکراری نباشد می‌گردد.
سج ویک یک ساده‌سازی ( اختصار ) از معماری مسیر همیلتون به این مسئله مختلف می‌دهد.
الگوریتم
بل من فورد در ساختار پایه‌ای‌اش بسیار شبیه به الگوریتم دایجکسترا است، ولی در عوض انتخاب حریصانه، گره با پایین‌ترین وزن که هنوز برای کاهش، پردازش نشده است را انتخاب می‌کند، که با این کار به سادگی تمام یال‌ها ی با وزن کم را انتخاب می‌کند. این الگوریتم این عملیات را در زمان ۱-|V| انجام می‌دهد، که|V| تعداد رئوس در گراف می‌باشد. تکرار، پایین‌ترین مسافت برای انتشار و توسعه دقیق خروجی ( بازدهی ) گراف فراهم می‌آورد، چون در غیاب دورهای منفی، کوتاهترین مسیر تنها می‌تواند هر نود را حداکثر یک بار ملاقات کند.
procedure BellmanFord(list vertices، list edges، vertex source)
// This implementation takes in a graph, represented as lists of vertices
// and edges, and modifies the vertices so that their distance and
// predecessor attributes store the shortest paths.
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then v.distance := 0
else v.distance := infinity
v.predecessor := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge uv in edges: // uv is the edge from u to v
u := uv.source
v := uv.destination
if u.distance + uv.weight <v.distance:
v.distance := u.distance + uv.weight
v.predecessor := u
// Step 3: check for negative-weight cycles
for each edge uv in edges:
u := uv.source
v := uv.destination
if u.distance + uv.weight <v.distance:
error "Graph contains a negative-weight cycle"
برعکس رویداد حریصانه، که وابسته به ساختار فرضی معین شده از وزن‌های مثبت است، این رویکرد حرکت رو به جلو (مستقیم، سر راست) به یک مورد عمومی را گسترش (توسعه) می‌دهد.
بل من فورد در زمان O(|V|*|E|) اجرا می‌شودکه به ترتیب تعداد رئوس و تعداد یال‌ها در گراف می‌باشند.
اثبات درستی
درستی این الگوریتم را بوسیله استنتاج ( قیاس ) می‌توان نشان داد.جمله مختصر ( دقیق ) که بوسیله استنتاج نشان داده می‌شود عبارت است از:
اصل موضوع:
بعد از i بار تکرار در حلقه for :
-اگر مسافت (U) بی‌نهایت نبود، برابر با طول بعضی مسیرها از S به U است.
-اگر مسیری ازS به U با حداکثر یال بود، پس مسافت (U) حداکثر طول کوتاهترین مسیرازS به U با حداکثر یال است.
اثبات :
برای حالت پایه‌ی استنتاج i=۰ و لحظه‌ای قبل از اینکه حلقه for برای اولین بار اجرا شود را در نظر بگیرید.بعد، برای راس مبدا source.distance=۰ را بگیرید، که درست است.
برای بقیه رئوسU ،U.distance=infinity، که همچنان صحیح است چون راهی از مبدا بهU با صفر یال وجود ندارد.
برای حالت استنتاجی ابتدا اولین قسمت را ثابت می‌کنیم. یک لحظه وقتی که یک مسافت راس بوسیله V.distance=U.distance+UV.weight به روز می‌شود را درنظر بگیرید. بوسیله فرض استنتاجی (قیاسی)U.distance طول بعضی مسیرها از مبدا به U است.پس U.distance+UV.weight طول مسیر از مبدا به V است که مسیری را از مبدا به Uو بعدV به می‌رود دنبال می‌کند(می‌گردد).
برای قسمت دوم، کوتاهترین مسیر از مبدا بهU را با بیشترین یال در نظر بگیرید. گیریم V آخرین راس قبل ازU در این مسیر باشد، بنابراین بخشی از مسیر از مبدا بهV کوتاهترین مسیر از مبدا بهV با حداکثر i-۱ یال است.بوسیله فرض استنتاجی، بعد از i-۱ دور در بیشترین طول این مسیر است. بنابراین،UV.weight + V.distance حداکثر طول مسیر ازS بهU است.درi امین دور، U.distance با UV.weight + V.distance مقایسه می‌شود و اگر UV.weight + V.distance کوچکتر بود برابر با آن می‌شود . بنابراین بعد ازi دور ، U.distance دربیشتر طول کوتاهترین مسیر از مبدا بهU است که بیشترین یال را انتخاب کرده‌است.
اگر دورها با وزن منفی وجود نداشته باشد، بنابراین هرکوتاهترین مسیری که هر راس را حداکثر ۱ بار ملاقات کند، در گام ۳ نمی‌تواند پیشرفت بیشتری بوجود آورد.
برعکس، درنظر بگیرید که هیچ پیشرفتی نتواند ساخته شده باشد، پس برای هر حلقه با رئوس V۰،V۱،……،Vk-۱
Vi.distance= V(i-۱) mod k.distance+ V(i-۱) mod kVi.weight
مجموع دور حلقه‌ها و Vi.distance مورد و V (i-۱) mod k مسافت مورد کنسل، باشد
۰ <= sum from ۱ to k of vi-۱ (mod k)vi.weight
برنامه‌های مورد استفاده در مسیر یابی
انتشارات مختلفی از الگوریتم بل من فورد در پروتکل Distance vector routing مورد استفاده قرار گرفته بود. برای مثال پروتکل RIP یکی از الگورتیم‌هایی است که انتشار یافته‌است چون تعدادی از گره‌ها (مسیر یاب‌ها) را با یک سیستم خود مختار درگیر می‌کند.یک مجموعه شبکه IP که معمولا بوسیله یک ISP مالکیت می‌شود شامل این گام‌ها می‌شود:
۱-هر گره مسافت بین خودش و تمام گره‌هایی که در داخل AS اند را محاسبه می‌کند و در جدولی اطلاعات را ذخیره می‌کند .
۲-هر گره جدول اش را به تمام نودهای مجاورش ارسال می‌کند.
۳-وقتی یک گره جدول مسافت را از گره مجاور خودش دریافت می‌کند، کوتاهترین مسیرها را به تمام بقیه گره‌ها محاسبه می‌کند و جدول خودش را برای بازتاب تغییرات بروز می‌کند.
اشکال اصلی الگوریتم بل من فورد در این تنظیمات عبارتست از :
-بخوبی مقیاس (نسبت) نمی‌کند.
-تغییر در توپولوژی شبکه به سرعت انعکاس داده نمی‌شود چون آپدیت شدن گره به گره منتشر می‌شود.
-محاسبه تا بی‌نهایت ( اگر لینک یا گره در انتقال به یک گره غیر قابل دسترس از بعضی از مجموعه دیگر گره‌ها شکست بخورد، آن گره‌ها ممکن است برای همیشه به تدریج تخمین مسافتشان به آن گره افزایش پیدا کند و در ضمن ممکن است مسیر loop باشد.)
توسعه YEN
در انتشار سال ۱۹۷۰ ، Jin.Y.Yen یک توسعه از الگوریتم بل من فورد را برای گراف بدون حلقه با وزن منفی تشریح کرد.توسعه Yen ابتدا کمی نوبت خطی انحصاری بر روی تمام رئوس و بعد تمام قسمت‌های مجموعه تمام یالها در یکی از ۲ زیر مجموعه نشان داد.اولین زیر مجموعه Ef۱ شامل تمام رئوس (Vi،Vj) که i<j و دومین مجموعه ، Eb شامل یال‌های (Vi،Vj) که i<j است. هر راس که در ترتیب v۱، v۲، …، v|V|، ملاقات می‌شود را کم می‌کند . هر خروجی یال از آن راس در Ef ثبت می‌شود.هر راس بعدی که در ترتیب v|V|، v|V|−۱، …، v۱ ملاقات می‌شود، هر خروجی از آن راس را در Eb کم می‌کند . توسعه Yen، تاثیرگذاری بسزایی در نصف کردن تعداد مسیرهای طی شده مورد نیاز برای مسئله کوتاهترین مسیر ممکن تک منبعی داشت.