אתגר אחרון מס׳ 1

שיעור 8 מתוך 9 בקורס אלגוריתם בלמן-פורד – אלגוריתמים על גרפים של Coddy.

אתגר

בינוני

הכוח המיוחד של Bellman-Ford הוא זיהוי מחזורים שליליים.

כתבו פונקציה בשם hasNegativeCycle שמקבלת את n ואת מערך edges השטוח (שלשות, מכוון) ומחזירה 1 אם הגרף מכיל מחזור שמשקלו שלילי, או 0 אחרת.

רמז: התחילו כל מרחק ב-0, בצעו הרפיה של כל הקשתות n - 1 פעמים, ואז בצעו מעבר נוסף. אם עדיין אפשר לבצע הרפיה של קשת כלשהי, קיים מחזור שלילי.

נסו בעצמכם

#include <stdlib.h>

int hasNegativeCycle(int n, int* edges, int edges_size) {
    // כתבו כאן את הקוד
    return -1;
}

כל השיעורים ביחידה אלגוריתם בלמן-פורד – אלגוריתמים על גרפים

1מבוא

2האלגוריתם

3אתגרים אחרונים