Sfida finale #1

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

Sfida

Medio

Il superpotere di Bellman-Ford è individuare i cicli negativi.

Scrivi una funzione chiamata hasNegativeCycle che accetta n e l'array edges lineare (terne, orientate) e restituisce 1 se il grafo contiene un ciclo di peso negativo, oppure 0 altrimenti.

Suggerimento: imposta ogni distanza a 0, rilassa tutti gli archi n - 1 volte, poi esegui un altro passaggio. Se un arco può ancora essere rilassato, esiste un ciclo negativo.

Provalo tu

#include <stdlib.h>

int hasNegativeCycle(int n, int* edges, int edges_size) {
    // Scrivi il codice qui
    return -1;
}

Tutte le lezioni di Algoritmo di Bellman-Ford - Algoritmi sui grafi

1Introduzione

Introduzione Motivazione

2L'algoritmo

Come funziona?Pseudocodice Implementazione (Parte 1)Implementazione (Parte 2)

Complessità temporale e spaziale

3Sfide finali

Sfida finale #1Sfida finale #2

Esercitati da solo: Compilatore C online