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