מימוש (חלק 2)

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

כעת נחשב את המסלול הקצר ביותר באופן חמדני.

אתגר

בינוני

עכשיו בנה את האלגוריתם המלא.

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

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

נסו בעצמכם

#include <stdlib.h>

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