يرجى إضافة وصلات داخلية للمقالات المتعلّقة بموضوع المقالة.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
خوارزمية فلويد-مارشل
Floyd-Warshall-Algorithm-Problem.png
بيانات عامّة
الصنف
بنية البيانات
المكتشف
تاريخ الاكتشاف
سمي نسبة لـ
الأداء
أسوء حالة
عدل القيمة على Wikidata
الحالة المُثلى
عدل القيمة على Wikidata
الأداء الوسطي
عدل القيمة على Wikidata
أسوأ حالة تعقيد مكاني
عدل القيمة على Wikidata

خوارزمية فلويد-مارشل في علوم الحاسب، خوارزمية فلويد-مارشل تستخدم لإيجاد أقصر طريق في رسم بياني موزون مع حدود موجبة أو سالبة الوزن (ولكن بدون دائرة سالبة).[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) إيجاد التعبير النمطي في لغة اعتيادية انعاكس المصفوفات الحقيقي

المراجع[عدل]

  1. ^ "معلومات عن خوارزمية فلويد-مارشل على موقع rosettacode.org"، rosettacode.org، مؤرشف من الأصل في 14 فبراير 2021.
  2. ^ "معلومات عن خوارزمية فلويد-مارشل على موقع xlinux.nist.gov"، xlinux.nist.gov، مؤرشف من الأصل في 28 أبريل 2021.