[Algoritmi] Algoritmi grafi

[cyrus2]

Salve, ho alcune difficoltà nel risolvere quest'esercizio:
" Si consideri un grafo orientato G in cui ad ogni nodo è associato il colore bianco o nero. Si descriva , fornendone il pseudocodice, un algoritmo per il calcolo dei cammini da un nodo sorgente ad ogni altro nodo con il minimo numero di nodi neri. Si calcoli la complessità computazionale."
Come dovrei procedere?

[apatriarca]

Qualsiasi algoritmo per il calcolo di cammini minimi in un grafo può essere usato. Ogni arco con destinazione un nodo nero avrà un costo uguale a 1 e tutti gli altri avranno costo nullo. Conosci qualche algoritmo per la ricerca di cammini minimi?

[cyrus2]

Algoritmo di Dijkstra, ma non so come modificarlo

[apatriarca]

È sufficiente dare un costo uguale a 1 ad ogni arco entrante in un nodo nero (ad esclusione del nodo destinazione se è nero) e uguale a zero per ogni arco entrante in un nodo bianco. A questo punto l'algoritmo è applicabile direttamente al tuo problema.

[cyrus2]

Come verrebbe?

[cyrus2]

A quanto ho capito, la differenza con l'algoritmo di Dijkstra è che devo considerare la lunghezza del cammino come il numero di nodi neri e non come la somma dei pesi