5
Devo trovare un percorso minimo da un'origine e una destinazione in cui origine e destinazione sono lo stesso nodo e voglio un numero fisso minimo di nodi nel percorso. Ho pensato di implementare un algoritmo Dijkstra (in Java) con la variante che i nodi k sono inclusi nel percorso minimo. (k è un numero minimo di nodi da coprire). È corretto? Se sì, qualche suggerimento per l'implementazione? Grazie in anticipovariante dijkstra con nodi k?
Un problema è che il nodo iniziale è contrassegnato quando si avvia. Devi smarcarlo – Blobonat
sì! Qualche idea sull'implementazione per i nodi k? – Denise
Questo è almeno difficile come risolvere il problema Hamiltonian Cycle NP-hard, dal momento che è possibile risolvere il problema semplicemente selezionando qualsiasi vertice come il vertice sorgente/destinazione, impostando k = n e quindi eseguendo l'algoritmo. –