Algoritmo per scoprire se esiste un percorso (qualsiasi percorso) sopra la lunghezza X tra due vertici

4

Sappiamo tutti come trovare il percorso più breve tra due vertici, ma cosa succede se voglio solo sapere la risposta a questa domanda - c'è un percorso (qualsiasi percorso), tra i vertici A e B di lunghezza più grande di alcuni X?

Dovrebbe iniziare dal percorso più breve e quindi unire i nodi adiacenti se la sua lunghezza è inferiore a X? (o estendere gradualmente la ricerca "cerchio")

Non voglio prima trovare tutti i percorsi possibili e poi filtrare quelli più brevi di X, voglio fermarmi nel momento in cui trovo un percorso sopra una certa lunghezza tra i due vertici, (e fermati se non ho trovato dopo alcune iterazioni MAX)

(presumo di fare prima un percorso più breve per trovare se c'è un qualsiasi percorso tra i nodi per evitare la ricerca se non c'è)

In qualche modo sembra che dovrebbe essere più semplice quello che sto facendo, ma non riesco a trovare un algoritmo per il libro di testo (es. BFS / DFS / Dijsktra / Bellman Ford non stanno aiutando proprio qui, giusto ?)

Sono sicuro che sia semplice, ma ho bisogno di una spinta nella giusta direzione.

    
posta Eran Medan 06.05.2015 - 04:08
fonte

1 risposta

1

Il problema che descrivi è la versione della decisione del problema del percorso più lungo (es. "Esiste un percorso di lunghezza almeno k? "). Come ha notato Jimmy Hoffa , il problema è NP-completo. Puoi esaminare gli algoritmi di approssimazione per LPP, in particolare quelli che sfruttano qualsiasi struttura speciale che i tuoi grafici potrebbero avere.

    
risposta data 15.05.2015 - 02:49
fonte

Leggi altre domande sui tag