Sfida finale #1

Lezione 8 di 9 del corso Ricerca in ampiezza - Algoritmi sui grafi di Coddy.

Sfida

Medio

È il momento dell'uso più caratteristico della BFS.

Scrivi una funzione chiamata shortestPath che accetta n, l'array piatto edges (non orientato), un vertice start e un vertice target, e restituisce la lunghezza del percorso più breve (il numero di archi) da start a target. Se target non è raggiungibile, restituisci -1.

Per esempio, in un percorso 0-1-2-3, il percorso più breve da 0 a 3 ha lunghezza 3.

Provalo tu

#include <stdlib.h>

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

Tutte le lezioni di Ricerca in ampiezza - 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