خوارزمية فلويد-مارشل

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (مايو 2021)

خوارزمية فلويد-مارشل

بيانات عامّة

الصنف	خوارزمية حساب مسار — خوارزمية مخصصة لبيان
بنية البيانات	بيان
المكتشف	برنارد روي
تاريخ الاكتشاف	1959
سمي نسبة لـ	روبرت فلويد — Stephen Warshall (en)

الأداء

أسوء حالة	${\displaystyle O(|n|^{3})}$
الحالة المُثلى	${\displaystyle O(|V|^{3})}$
الأداء الوسطي	${\displaystyle O(|V|^{3})}$
أسوأ حالة تعقيد مكاني	${\displaystyle O(|V|^{2})}$

تعديل - تعديل مصدري - تعديل ويكي بيانات

خوارزمية فلويد-مارشل في علوم الحاسب، خوارزمية فلويد-مارشل تستخدم لإيجاد أقصر طريق في رسم بياني موزون مع حدود موجبة أو سالبة الوزن (ولكن بدون دائرة سالبة).^[1][2] عندما استخدام الخوارزمية، سوف تجد نتيجة مجموع أوزان الأطوال لأقصر لطريق بين رؤوس الرسم البياني. هذه الخوارزمية لا تعطي تفاصيل الطريق ولكن يمكن أن تعيد إنشاء الطريق باستخدام تعديلات من الخوارزمية. 

خوارزمية فلويد-مارشل هي مثال على البرمجة الديناميكية. الاسم مقتبس من روبرت فلويد في 1962 ولاحقا انضم ستيفن ورشيل لوجود الإغلاق المتعدد للرسم. الخورامية تسمى أيضًا: خوارزمية فلويد، خوارزمية روي ورشل، خوارزمية روي فلويد.

الخوارزمية تقارن جميع الطرق الممكنة في رسمة. يكون من خلال مقارنة في رسمة.

السودو كود لهذه الخوارزمية هو كالتالي:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each edge (u,v)
3    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
4 for each vertex v
5    dist[v][v] ← 0
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

إيجاد أقصر طريق في رسمة مباشرة (Directed graph) الإغلاق المتعدد للرسمة المباشرة (Transitive closure of directed graph) إيجاد التعبير النمطي في لغة اعتيادية انعاكس المصفوفات الحقيقي

هذه بذرة مقالة عن الحاسوب أو العاملين في هذا المجال، بحاجة للتوسيع. فضلًا شارك في تحريرها.