كيف تعالج خوارزمية توجيه متجه المسافة دورات الوزن السلبية؟

Question

هناك عدد قليل من الأسئلة هنا على هذه الخوارزمية ، لكنني لم أتمكن من العثور على كيف ستتعامل مع دورات الوزن السلبية؟ لنفترض أن جهاز التوجيه x يحصل على تحديث من جهاز التوجيه y بأن تكلفة y إلى Z هي 5. في وقت لاحق ، يتم تحديث جهاز التوجيه X من جهاز التوجيه y أن تكلفة y إلى Z هي الآن. ماذا يفعل جهاز التوجيه x؟ أفهم أن خوارزمية بيلمان فورد تنص على أنه ينبغي رفع الخطأ في هذه الحالة. ولكن ما هي خوارزمية توجيه ناقلات المسافة التي تقوم بها - ما عليك سوى تحديثه أو رفع خطأ أو أي شيء آخر؟

Answer 1

لست متأكدًا مما إذا كنت أقرأ هذا السؤال بشكل صحيح. يمكن للتحديثات من أجهزة التوجيه تحديد تكلفة جديدة لمسار ما إذا كان أعلى أو أقل من ذي قبل. إذا حصل X على تحديث من Y للحصول على مسار إلى Z بتكلفة 2 (في الأصل 5) ، فيجب على X ببساطة تحديث جدول إعادة التوجيه الخاص به بمسار التكلفة الجديد واستخدام هذا المسار للوصول إلى Z إذا كان مسار التكلفة الأقل.

Answer 2

لديك تعارض بين انخفاض تكلفة Bellman-Ford Algortihm وتحديث القفز التالي لتكلفة الرابط ، يمكن القيام الأول بين اثنين أو أكثر واجهات مختلفة للحصول على تكلفة أرخص ، لـ exemple:

** الحالة 1: ** جهاز التوجيه A لديه 3 جيران N1 و N2 و N3 و N1 و N2 و N3 لديهم X كجيران

|---2----N1-----4----|
A`--4----N2-----3----X
|---1----N3-----2----|

لجهاز التوجيه أ:

 X via N1 =6 
 X via N2=7            the lowest is :**X Via N3=3**
 X Via N3=3

-الد هنا ، سوف تختار X عبر N3 (بين N1 ، N2 ، N3) لأنه هو الأخفض واحد الحالة 2: إذا تم تغيير تكلفة الارتباط بين (x-n3 = 2) إلى (x-n3 = 8) ، نفترض بسبب تكوين الرابط (حتى 8 أكثر من 2 ولكنه التزام) ، يجب على N3 إبلاغ أ عن ذلك و يجب تحديث التكلفة من (x عبر n3 = 3) إلى (x عبر n3 = 9) ، وبالتالي نعود إلى الحالة (1): اختر أقل تكلفة ستكون عبر N1

     X via N1 =6 
     X via N2=7            ****the lowest is :**X Via N1=6******
     X Via N3=9