מימוש (חלק 1)

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

ראשית, מעבר הרפיה יחיד על כל הקשתות.

אתגר

בינוני

Bellman-Ford היא פעולה אחת בלבד שחוזרת על עצמה: מעבר הרפיה על כל הקשתות. בואו נבנה מעבר יחיד.

כתבו פונקציה בשם 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;
}