Ho bisogno di un algoritmo che dati due nodi di un grafo orientato e con archi pesati, mi trovi tutti i percorsi dal primo nodo al secondo nodo e il peso totale di ogni percorso.
Quale algoritmo dovrei usare?
Stavo pensando a Dijkstra, ma serve a trovare il percorso più breve, non tutti i percorsi esistenti.
Se il grafo è aciclico, ti basta fare una visita in profondità o in ampiezza come se fosse un albero n-ario.
Già, dimenticavo, ci sono dei cicli e i percorsi che li contengono andrebbero eliminati dal risultato.
se ci sono dei cicli, allora devi accorgertene durante la visita perchè le visite "standard" in ampiezza/profondità terminano solo quando arriva alle foglie; per cui entreresti in un ciclo infinito.
Permessi di invio
Rispondi quotando