KTH PATURA più breve

Question

Qualcuno sa come posso scrivere un grafico di programmazione (il codice C ++ sarebbe fantastico) che trova il percorso più breve KTH per un determinato set di nodi e bordi in un grafico ciclico?

Ad esempio, il percorso più breve (che potrebbe essere trovato da Dijkstra o Bellman Ford) è considerato il primo percorso più breve. Ora il secondo percorso più breve è il più corto che arriva dopo il primo percorso più breve. Ora voglio che l'algoritmo trovi il percorso più breve KTH. Ti viene dato il numero di nodi, bordi e set di bordi, come segue:

Numero di nodi: 5
Numero di bordi: 6
bordi:
0 1
0 2
1 2
2 3
3 1
1 4
Nodo di origine: 0
nodo di destinazione: 4

"Nota che questo grafico contiene un ciclo" Grazie.

Answer 1

Usare un Ricerca sui costi uniforme algoritmo. Dove la Wikipedia dice "Soluzione di ritorno", non smettere e return ma aggiungi il risultato a qualche elenco fino a quando quell'elenco non contiene K percorsi. Il K'L'elemento dell'elenco (contando da 1) sarà il K'th percorso più breve.

Non tenere un set "chiuso"/"esplorato" o questo algoritmo non funzionerà correttamente.