مرجع
آخر الزيارات

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

217 كلمة•0 مشاهدة•🗒️ منذ 4 أيام
باختصار: خوارزمية فلويد-مارشل في علوم الحاسب، خوارزمية فلويد-مارشل تستخدم لإيجاد أقصر طريق في رسم بياني موزون مع حدود موجبة أو سالبة الوزن (ولكن بدون دائرة سالبة). تجد هنا «التاريخ والتسمية»، «الاستعمالات والتطبيقات» و«خوارزمية فلويد-مارشل» ضمن 4 أقسام.
المحتويات
  1. التاريخ والتسمية
  2. الاستعمالات والتطبيقات
  3. خوارزمية فلويد-مارشل
  4. الخوارزمية
خوارزمية فلويد-مارشل

التاريخ والتسمية

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

إضافةً إلى ذلك، الخورامية تسمى كذلك: خوارزمية فلويد، خوارزمية روي ورشل، خوارزمية روي فلويد.

الاستعمالات والتطبيقات

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

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

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

من جهة ثانية، هذه الخوارزمية لا تعطي تفاصيل الطريق ولكن يمكن أن تعيد إنشاء الطريق باستخدام تعديلات من الخوارزمية.

الخوارزمية

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

  • 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

وفي هذا السياق، السودو كود لهذه الخوارزمية هو كالتالي:1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.