إذا كان الرسم البياني يحتوي على دورات ذات وزن سلبي ، فإن خوارزمية 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) \) يمكن أن يكون ذا أطوال متناهية الصغر.