Percorso più breve
Lezione 12 di 14 del corso Grafi - Serie sulle strutture dati #9 di Coddy.
Quanti meno archi servono per andare da start a end? In un grafo non pesato (ogni arco ha lo stesso costo), la risposta è esattamente ciò che calcola BFS. Poiché BFS visita i vertici in ordine di distanza crescente dalla partenza, la prima volta che raggiungiamo end è lungo un percorso più breve.
Il trucco è accodare ogni vertice insieme alla distanza percorsa finora. Inizia con (start, 0). Ogni volta che scopri un nuovo vicino v da un vertice a distanza d, accoda (v, d + 1). Quando v == end, restituisci d + 1.
Due casi limite. Se start == end, la risposta è 0. Se BFS termina senza aver mai raggiunto end, i due vertici si trovano in componenti connesse diverse e la risposta è -1.
Sfida
FacileScrivi una funzione shortestPath che riceve un array 2D di int adjacency, un int start e un int end, e restituisce la distanza minima (numero di archi) da start a end.
- Se
start == end, restituisci0. - Se
endnon è raggiungibile dastart, restituisci-1. - Altrimenti, restituisci il numero minimo di archi tra i due.
Devi usare la classe Graph (fornita in graph): non usare le strutture integrate del linguaggio (mappe, insiemi) per rappresentare l’adiacenza. I dati ausiliari per l’algoritmo (insiemi dei nodi visitati, code) possono usare tipi della libreria standard.
Provalo tu
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}
Tutte le lezioni di Grafi - Serie sulle strutture dati #9
Esercitati da solo: Compilatore C online