Breadth First Search to find route between two underground stations

Hi I am creating a program to find a route between two station in the London underground. I am using linked objects to represent the network. So a station object contains: the name, list of the lines which the station is in, the list of stations it is adjacent to. I also have line objects which contain: the name, list of stations of the line. And also a network object which contain the list of all the stations and list of all the lines.

I was thinking of using breadth first search but am confused on how to implement the algorithm on my data structure. Any help would be appreciated.

I also used a different method to find the route, searching the lines of the source if it contains the destination. If it doesnt then looking at the junctions in the lines ie stations with more than 1 line. and looking at their lines and seeing if the destination is in those. But after 1 change i got confused on how to do more than one change. heres the code which i used:

public void finder(String from, String to)
{

    Station source = network.searchStation(from);
    Station destination = network.searchStation(to);
    ArrayList<Line> sourceLines = source.getLines();
    ArrayList<String> routes = new ArrayList<String>();

    for(Line line:sourceLines)
    {
        ArrayList<Station> stations = line.getStations();
        if(stations.contains(destination))
        {
            Station endStart;
            if(stations.indexOf(destination) > stations.indexOf(source))
            {
                endStart = stations.get(stations.size()-1);
            }
            else{
                endStart = stations.get(0);
            }
            routes.add(endStart.getName());
            routes.add(line.getName());
            break;
        }
    }
    if(routes.size() != 0)
    {
        System.out.println("Start: "开发者_运维知识库 + from);
        System.out.println("Take the " + routes.get(1) + " line towards " + routes.get(0));
        System.out.println("End: " + to);
    }
    else{
        routes = search(source, destination, routes);
        System.out.println("Start: " + from);
        for(int n = 0; n < (routes.size() / 6);n++)
        {
            System.out.println("Take the " + routes.get(n + 1) + " line towards " + routes.get(n));
            System.out.println("Change at: " + routes.get(n + 2) + " to the " + routes.get(n + 3) + " line");
            System.out.println("Take the " + routes.get(n + 5) + " line towards " + routes.get(n + 4));
        }
        System.out.println("End: " + to);
    }
}

public ArrayList<String> search(Station source, Station destination, ArrayList routes)
{
    ArrayList<Line> sourceLines = source.getLines();
    for(Line line:sourceLines)
    {
        ArrayList<Station> searchList = new ArrayList<Station>();
        ArrayList<Station> lineStations = line.getStations();
        if(line.getVisited() == false)
        {
            for(Station station: lineStations)
            {
                if(station.getLines().size() > 1)
                {
                    searchList.add(station);
                }
            }
        }

        for(Station station:searchList)
        {
            ArrayList<String> stationChanges = new ArrayList<String>();
            ArrayList<Line> lines = station.getLines();
            Station endLine;
            if(lineStations.indexOf(station) > lineStations.indexOf(source))
            {
                endLine = lineStations.get(lineStations.size()-1);
            }
            else{
                endLine = lineStations.get(0);
            }
            stationChanges.add(endLine.getName());
            stationChanges.add(line.getName());
            for(Line stationLine:lines)
            {
                ArrayList<Station> stations = stationLine.getStations();
                if(stations.contains(destination))
                {
                    stationChanges.add(station.getName());
                    stationChanges.add(stationLine.getName());
                    Station endStart;
                    if(stations.indexOf(destination) > stations.indexOf(station))
                    {
                        endStart = stations.get(stations.size()-1);
                    }
                    else{
                        endStart = stations.get(0);
                    }
                    stationChanges.add(endStart.getName());
                    stationChanges.add(stationLine.getName());
                    for(String str:stationChanges)
                    {
                        routes.add(str);
                    }
                    return routes;
                }
                else
                {
                    stationLine.markVisited();
                    search(station,destination,stationChanges);
                }
            }

        }
    }
    return routes;
}

Thanks

Routing is different problem altogether. You need to use dijkstra's algorithm or variations to it, simple BFS or backtracking kind of algorithms without much thought might leave you astray!

You should use Dijkstra's algorithm. Breadth-first search will probably find a route, but not an optimal one. You can use 1 as a constant edge weight, to get the shortest route in the number of stations.

Sounds like you haven't got cost data so you should just use BFS.

This post might give you a few pointers: Finding a route on the Underground using pure Java code

you need to weight each node and find the route with the less weight. If you just do bread First, that will return the first route that matches, which might be miles away from the optimal route.

For example, going from adjacent stations on the same line weights 1, changing to another line weights 2. If you want to go from Notthing Hill Gate to Holland Park, then the total weight is 1. If you want to go from Bayswater to Holland Park, the weight is 4 (1 for station, 2 for line change, 1 for station)

I'm not an expert of this, but for me it sounds like a backtracking algorithm, to find the optimal route.

And to top it all off, given the nature of the problem, you may want to implement an extra penalty on changing lines.

After all, if you're travelling central line and changing to northern to cut a few minutes off the travel time, you likely find yourself taking more than those few minutes to get to the northern line platform and wait for the next train to arrive there. Can't put those costs into the cost of the node, as it would only apply for some of the incoming/outgoing vertex combos on that node (and the penalty could even be different for different combos if you want to get real fancy and measure actual time needed to change lines on the Tube).