Implementazione (Parte 2)

Lezione 6 di 9 del corso Algoritmo di Dijkstra - Algoritmi su grafi di Coddy.

Ora il calcolo greedy del percorso più breve.

Sfida

Medio

Ora costruisci l’algoritmo completo.

Scrivi una funzione chiamata dijkstra che accetta n, l’array edges piatto (triple, dirette, con pesi non negativi) e un source, e restituisce un array in cui la posizione v contiene la distanza minima da source a v. Usa -1 per i vertici che non possono essere raggiunti.

Imposta tutte le distanze a un valore grande, «infinito», tranne quella della sorgente, che sarà 0. Poi, per n volte, rendi definitivo il vertice non visitato più vicino e rilassa i suoi archi uscenti.

Provalo tu

#include <stdlib.h>

int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
    // Scrivi il codice qui
    *returnSize = 0;
    return edges;
}