cammino minimo per lista di picking: nodi "imposti" da visitare

Rob123

Nuovo Utente
26 Ago 2020
1
0
1
salve ragazzi, sto cercando di districarmi in un problema di cammino minimo su grafo di 14 nodi corrispondenti a reparti. Data una certa lista di picking ho solo alcuni dei nodi da visitare per forza, e vorrei ordinare la lista per cammino minimo. Ragionando sull'algoritmo di Dijkstra, applicandolo sul grafo completo otterrei il cammino minimo dal nodo 0 (magazzino) ad un nodo finale, ma a me serve "imporre" reparti che devono essere visitati per forza. Se considerassi un sotto grafo che contenga solo i nodi che voglio visitare e applicassi Dijkstra su questo sotto grafo, andrebbe si a visitare tutti i nodi ma poi restituirebbe in output comunque un cammino minimo che non contiene tutti i nodi. come risolvo quindi il problema del cammino minimo di questo genere? grazie mille in anticipo
 

marino51

Utente Attivo
28 Feb 2013
2.927
166
63
Lombardia
se ho capito bene il problema,
potresti agire sulle diverse sezioni del grafo, come nel caso di un percorso a tappe
supponendo di muoversi da 0 a 14, con obbligo di passare da 7 e 10,
potresti cercare il cammino minimo da 0 a 7 poi da 7 a 10 e infine da 10 a 14 (sempre se le visite obbligate sono in sequenza)
l'insieme dei 3 risultati potrebbe soddisfare la necessità
fai sapere