[Java] Ricercapercorsi in un multigrafo

[Alhazred]

Il multigrafo qui sopra rappresenta un'ipotetica rete metropolitana.
Le lettere sono i nomi delle stazioni, i numeri sono i nomi delle linee (bidirezionali).

Date due stazioni qualsiasi, devo trovare tutti i percorsi possibili, scartando quelli che mi fanno usare la stessa linea alternata ad un'altra.
Ad esempio da A a F il percorso
A --(linea 1)--> B --(linea 1)--> C --(linea 2)--> F
è un percorso buono, invece
A --(linea 2)--> B --(linea 1)--> C --(linea 2)--> F
andrebbe scartato

Fin quando si tratta di un grafo semplice (quindi una sola linea tra due stazioni) non ho problemi, ho già scritto il codice e fa tutto quello che deve fare, uso una BFS per trovare i percorsi.

Il problema è che non so come modificare l'algoritmo in modo che controlli tutti i percorsi tenendo in considerazione che si tratta di un multigrafo.

Di seguito riporto la parte che mi fa la ricerca dei percorsi.
Come già detto, in caso di grafo semplice funziona, con un multigrafo no.

Qualcuno saprebbe indicarmi come modificare il codice?
Se necessario posso fornire il codice di tutte e 5 le classi in modo che se volete potete testarlo.

Codice PHP:

public List<Path> bfs(GraphImpl<String,Integer> g,
                              LinkedList<VertexImpl<String>> visited,
                           List<Path> paths,
                           VertexImpl<String> destination) {

        //vertici raggiungibili dal vertice corrente
        Collection<VertexImpl<String>> nodes = g.outVertices(visited.getLast());
        // esamina i vertici adiacenti
        for (VertexImpl<String> node : nodes) {
            if (visited.contains(node)) { //se il vertice corrente è già stato visitiato
                continue;
            }

            if (node.equals(destination)) { //se il vertice corrente è quello di destinazione
                visited.add(node);

                boolean buono   = true;        //dice se il percorso è buono
                boolean inarray = false;    //dice se una linea è già nell'array

                Iterator<VertexImpl<String>> li = visited.iterator();
                VertexImpl<String> v1 = null;
                VertexImpl<String> v2 = null;
                String lineaTemp = "";
                String[] linee = new String[20];
                for(int k=0; k<20; k++) linee[k] = "";
                int i = 0;

                v1 = li.next();
                while(li.hasNext()) {
                    v2 = li.next(); //vertice di arrivo

                    EdgeImpl<String,Integer> edge = g.getEdge(v1,v2); //arco che conginge v1 e v2

                    if(lineaTemp.equals("")) { //è la prima tratta
                        lineaTemp = edge.getLine();
                        linee[i]  = edge.getLine();
                        i++;
                    } else { //non è la prima tratta
                        if(!lineaTemp.equals(edge.getLine())) {         //se la linea attuale è diversa dalla precedente (se c'è stato un cambio di linea)
                               for(int j=0;j<linee.length;j++) {             //per ogni linea già presa in considerazione
                                   if(linee[j].equals(edge.getLine())) {     //se una è uguale a quella attuale
                                       inarray = true;                        //indico che è stata trovata
                                   }
                               }
                               if(!inarray) { //se la linea corrente non era stata presa in considerazione
                                   lineaTemp = edge.getLine(); //aggiorno l'ultima linea presa in considerazione
                                   linee[i]  = edge.getLine(); //aggiungo la linea alla lista delle linee
                                   i++;
                               } else { //si è tornati su una linea utilizzata in precedenza per lo stesso percorso, non va bene
                                   buono = false;     //il percorso non è buono
                                   inarray = false; //resetto la variabile inarray
                               }
                        } else { //il percorso è buono
                            buono = true;
                            inarray = false;
                        }
                    }

                    v1 = v2;
                }

                if(buono) { //se il percorso è buono lo aggiungo alla lista dei percorsi
                    //codice omesso per brevità
                }

                   visited.removeLast();
                break;
            }
        }

        //ricorsione per la BFS
        for (VertexImpl<String> node : nodes) { //per tutti i vertici raggiungibili da quello corrente
            if (visited.contains(node) || node.equals(destination)) { //se è già stato visitato o se è quello cercato
                continue;
            }
            visited.addLast(node); //segna il vertice come visitato
            bfs(g, visited, paths, destination); //chiamo ricorsivamente la funzione bfs
            visited.removeLast(); //rimuovo l'ultimo vertice visitato
        }

        return paths; //ritorno i percorsi trovati
    } 


[Alhazred]

Si, agli archi sono associati dei pesi.
Comunque il fatto di scartare il secondo percorso che ho indicato è perché ti fa partire da A prendendo la linea 2, arrivato in B ti fa cambiare e prendere la linea1, poi di nuovo alla fermata seguente ti fa prendere la linea iniziale.
Tu da viaggiatore faresti mai una cosa simile?

Non lo scarto perché è un percorso sbagliato, ma perché non è logicamente accettabile.