Implementazione (Parte 1)

Lezione 5 di 9 del corso Algoritmo di Bellman-Ford - Algoritmi sui grafi di Coddy.

Per prima cosa, un singolo passaggio di rilassamento su tutti gli archi.

Sfida

Medio

Bellman-Ford è semplicemente un’operazione ripetuta: un passaggio di rilassamento su tutti gli archi. Creiamo un singolo passaggio.

Scrivi una funzione chiamata relaxAll che accetta n, l’array piatto edges (terne, orientate, eventualmente negative) e una source. Inizia con dist[source] = 0 e tutti gli altri valori impostati all’infinito, poi rilassa ogni arco una volta (nell’ordine dato) e restituisci le distanze risultanti, usando -1 per i vertici ancora irraggiungibili.

Poiché è un solo passaggio, i vertici raggiungibili solo attraversando diversi archi potrebbero avere ancora valore -1. È previsto.

Provalo tu

#include <stdlib.h>

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