Implementation (Part 2)
الدرس 6 من 9 في دورة خوارزمية Bellman-Ford - خوارزميات المخططات على Coddy.
الآن كرر التمريرة حتى تصبح المسافات نهائية.
التحدي
متوسطالآن الخوارزمية الكاملة: كرر عملية الاسترخاء (relaxation) حتى تستقر المسافات.
اكتب دالة باسم bellmanFord تأخذ n، ومصفوفة edges المسطحة (ثلاثيات، موجهة، قد تكون سالبة)، و source، وتعيد أقصر مسافة من source إلى كل رأس. استخدم -1 للرؤوس التي لا يمكن الوصول إليها. افترض عدم وجود دورة سالبة (negative cycle).
قم بعمل استرخاء (Relax) لجميع الحواف n - 1 من المرات.
جرّب بنفسك
#include <stdlib.h>
int* bellmanFord(int n, int* edges, int edges_size, int source, int* returnSize) {
// اكتب الكود هنا
*returnSize = 0;
return edges;
}
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس خوارزمية Bellman-Ford - خوارزميات المخططات
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity