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

الگوریتم

بل من فورد در ساختار پایه‌ای اش بسیار شبیه به الگوریتم دایجکسترا است، ولی در عوض انتخاب حریصانه، گره با پایین‌ترین وزن که هنوز برای کاهش، پردازش نشده‌است را انتخاب می‌کند، که با این کار به سادگی تمام یال‌ها ی با وزن کم را انتخاب می‌کند. این الگوریتم این عملیات را در زمان ۱-|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[۱]،……،V[k-۱]
V[i].distance= V[(i-۱) mod k].distance+ V[(i-۱) mod k]V[i].weight
مجموع دور حلقه‌ها و V[i].distance مورد و V [(i-۱) mod k] مسافت مورد کنسل، باشد 
۰ <= sum from ۱ to k of v[i-۱ (mod k)]v[i].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، تأثیرگذاری بسزایی در نصف کردن تعداد مسیرهای طی شده مورد نیاز برای مسئله کوتاهترین مسیر ممکن تک منبعی داشت.