Java - поиск в ширину на мультиграфе полетов

У меня есть граф с городами как узлами и классом Flight как ребра. У каждого рейса есть время вылета, время прибытия, номер рейса и массив дней, в которые он выполняется. Несколько ребер могут соединять каждую пару узлов, делая граф мультиграфом. Мне нужно ответить на вопрос: Какие рейсы доступны из Place1 в Place2 в данный день и возможны пересадки?

Следующие два метода используют поиск в глубину для поиска и печати ответа:

public static void printRoutes(String day,String source,String place1, String place2, boolean[] visited, LinkedList<Edge> Route,Grafo g) {

    int index = hash.get(place1);
    visited[index] = true;


    if (place1.equals(place2)) 
        if (isTransferable(day,Route,source))
            writeRoute(Route,source);

    if (place1 != place2) {
        LinkedList<Edge> adjs = g.adjs_no(place1);


        for(Edge a: adjs) {
            if (!visited[hash.get(a.node_final)]) {
                Route.add(a);
                printRoutes(day,source,a.node_final,place2,visited,Route,g);
                Route.remove(a);
            }
        }
    }
    visited[indice] = false;            
}

public static void writeRoute(LinkedList<Edge> Route,String source) {
        System.out.print(source + " -> ");
        for (int i = 0; i < Route.size(); i++) {
            System.out.print(Route.get(i).vertex_final() + " | Flight Number:");
            System.out.print(Route.get(i).flight.flightNumber + " | Departure Time:" + Route.get(i).flight.departureTime);
            System.out.println();
            if (i != Route.size()- 1)System.out.print(Route.get(i).vertex_final() + " -> ");

        }
        System.out.println();
        System.out.println();    
    }

isTransferable проверяет, существует ли промежуток времени между прибытием и вылетом двух рейсов не менее 40 минут.

Я хотел бы ответить на этот вопрос, используя поиск в ширину вместо DFS, чтобы сначала появлялись более короткие поездки. Однако алгоритм, который у меня есть для BFS, не работает для мультиграфов. Есть ли способ выполнить BFS на этом графике, чтобы я мог успешно распечатать все возможные поездки между двумя городами в заданный день?