pensando ad un grafo, se devi andare da un nodo sorgente ad un nodo destinazione, potresti trovare il percorso minimo ed eliminare/marcare la connessione tra il nodo destinazione e il nodo subito prima.
cioe' se questo fosse il percorso minimo tra sorgente e destinazione

sorgente-->O1-->O2--> ... -->On-->destinazione

una volta che lo modifichi cosi':

sorgente-->O1-->O2--> ... -->On (arco eliminato) destinazione

basta cercare sul nuovo grafo il cammino minimo, eliminare l'ultimo arco del cammino e continuare finche' non ci sono piu' cammini tra i due nodi.

La mia e' solo un'idea ma non so quale sia la tua struttura dati, non so nemmeno se hai un grafo aciclico o no... insomma occhio che se cerchi tutte le strade per andare da un punto ad un altro cerchi anche la strada piu' lunga che non si' puo' determinare perche' si puo' passare dal brasile per andare dalla sala al bagno :P