Implementation (Part 1)
الدرس 5 من 9 في دورة خوارزمية Bellman-Ford - خوارزميات المخططات على Coddy.
أولاً، تمريرة استرخاء واحدة على جميع الحواف.
التحدي
متوسطخوارزمية Bellman-Ford هي مجرد عملية واحدة متكررة: تمريرة استرخاء (relaxation pass) على جميع الحواف. لنقم ببناء تمريرة واحدة.
اكتب دالة باسم relaxAll تأخذ n، ومصفوفة edges مسطحة (ثلاثيات، موجهة، وربما سالبة)، و source. ابدأ بـ dist[source] = 0 وجميع المسافات الأخرى عند اللانهاية، ثم قم بعمل استرخاء لكل حافة مرة واحدة (بالترتيب المعطى) وأرجع المسافات الناتجة، مع استخدام -1 للرؤوس التي لا تزال غير قابلة للوصول.
بما أنها تمريرة واحدة فقط، فإن الرؤوس التي يمكن الوصول إليها فقط من خلال عدة حواف قد تظل -1. هذا أمر متوقع.
جرّب بنفسك
#include <stdlib.h>
int* relaxAll(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