Error

إذا كان الرسم البياني يحتوي على دورات ذات وزن سلبي ، فإن خوارزمية Floyd-Warshall لا تنطبق رسميًا على مثل هذا الرسم البياني.

في الواقع ، بالنسبة لأزواج القمم i & nbsp ؛ و j ، والتي من المستحيل الدخول بينها في دورة من الوزن السالب ، ستعمل الخوارزمية بشكل صحيح.

بالنسبة إلى نفس أزواج الرؤوس التي لا توجد إجابة لها (نظرًا لوجود دورة سالبة على المسار بينهما) ، ستجد خوارزمية Floyd عددًا ما (ربما يكون سالبًا بشدة ، ولكن ليس بالضرورة) كإجابة. ومع ذلك ، يمكن تحسين خوارزمية فلويد للتعامل مع أزواج القمم هذه بدقة وإخراجها على سبيل المثال & nbsp؛ \ (- \ infty \) .

للقيام بذلك ، على سبيل المثال ، يمكن إجراء & nbsp؛ المعيار التالي & quot؛ عدم وجود المسار & quot؛. لذا ، دع خوارزمية فلويد المعتادة تعمل على هذا الرسم البياني. ثم لا يوجد أقصر مسار بين الرؤوس i & nbsp ؛ و j & nbsp ؛ إذا وفقط إذا كان هناك قمة يمكن الوصول إليها من i & nbsp ؛ ومن خلالها يمكن الوصول إلى j ، والتي & nbsp ؛ \ (d [t] [t] & lt؛ 0 \) .

بالإضافة إلى ذلك ، عند استخدام خوارزمية Floyd للرسوم البيانية ذات الدورات السالبة ، يجب أن نتذكر أن المسافات التي تنشأ في عملية العمل يمكن أن تذهب سلبًا ، أسيًا مع كل مرحلة. لذلك ، يجب أن تحذر من تجاوز العدد الصحيح من خلال قصر جميع المسافات من الأسفل على بعض القيم (على سبيل المثال ، & nbsp؛ \ (- \ infty \) ).

شفهيًا ، يمكن وصف الحل على النحو التالي:
بعد عمل خوارزمية Floyd-Warshall للرسم البياني للإدخال ، دعنا نكرر جميع أزواج الرؤوس & nbsp؛ \ ((i، j) \) ولكل زوج من هذه الأزواج نتحقق ، إلى ما لا نهاية ، أقصر طريق من i & nbsp ؛ إلى j & nbsp ؛ صغير أم لا. للقيام بذلك ، دعنا نكرر على الرأس الثالث t ، وإذا اتضح أنه & nbsp؛ \ (d [t] [t] & lt؛ 0 \) & nbsp؛ (أي أنها تقع في دورة الوزن السالب) ، ويمكن الوصول إليها من i & nbsp ؛ و j & nbsp ؛ & [مدش] ؛ ثم المسار & nbsp؛ \ ((i، j) \) يمكن أن يكون ذا أطوال متناهية الصغر.

نظرًا لأن خوارزمية Floyd ترخي بالتتابع المسافات بين جميع أزواج القمم (i ، j) ، بما في ذلك تلك التي تحتوي على i = j ، والمسافة الأولية بين زوج من القمم (i ، i) تساوي صفرًا ، عندئذٍ يمكن أن يحدث الاسترخاء فقط إذا كان الرأس k مثل d [i] [k] + d [k] [i] & lt؛ 0 ، وهو ما يعادل وجود دورة سالبة من خلال الرأس i

يمكنك قراءة المزيد حول العثور على دورة سلبية هنا: http://e-maxx.ru/algo/export_ford_bellman

يصبح المسار عبر دورة الوزن السلبي مستحيلاً.