מימוש (חלק 2)

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

כעת חזרו על המעבר עד שהמרחקים יהיו סופיים.

אתגר

בינוני

כעת האלגוריתם המלא: חזור על שלב ההרפיה עד שהמרחקים מתייצבים.

כתוב פונקציה בשם bellmanFord שמקבלת את n, את מערך edges השטוח (שלשות, מכוונות, ייתכן שמשקליהן שליליים), ואת source, ומחזירה את המרחק הקצר ביותר מ־source לכל קודקוד. השתמש ב־-1 עבור קודקודים שאינם נגישים. הנח שאין מעגל שלילי.

הרפה את כל הקשתות n - 1 פעמים.

נסו בעצמכם

#include <stdlib.h>

int* bellmanFord(int n, int* edges, int edges_size, int source, int* returnSize) {
    // כתבו כאן את הקוד
    *returnSize = 0;
    return edges;
}