Find fastest connection to a certain point

Question

What i'm trying to implement is a program that is searching for the fastest connection from one station to other at a given time of the day.

I have a number of stations n, and a number m of lines that connect this stations. Each line has (departStation, arrivalStation, busDepartTime, busTravelTime).

When I want to search for a connection from station A to B I will have the input (from, to, myDepartTime).

If I started to think correctly, the stations will be Vertexes and each line will be a edge. I wanted to use Dijkstra's algorithm to implement this, but I'll find the shortest travel time of a bus (see example 1).

What I need to change in code to get the wanted result as in example 1? Is there any other algorithm I can use? Maybe a better one? Or just some tips?

I need to know if I'm on my right way. I'm just trying to create a simple command line program, nothing to complex.

I'm thinking about calculating the time I need to wait until the bus departs and the total duration of travel and then to choose the shortest from all. The only problem is that I don't really understand how I can implement this.

Example 1:

4 stations: 0, 1, 2, 3

4 lines(connections)

Note: depart times are given in minutes from the start of the day (120 -> 02:00)

(departStation, arrivalStation, busDepartTime, busTravelTime)

(0, 1, 10, 30), (0, 1, 70, 30), (0, 2, 130, 10), (1, 2, 60, 30), (1, 3, 100, 60), (3, 1, 30, 20)

Now, I need to get from 0 to 2 at 00 (0, 2, 00) Dijkstra's algorithm I have, will return the shortest busTravelTime which is 30 and will print the path 0 - > 2(10). That's great, but is not good because I need to wait 130 min. What will be great is to get the path 0 -> 1(30) -> 2(60) because the bus is leaving at 30 and I need to wait only 10 min.

Here is the code:

import java.util.*;

public class Dijkstra2 {
    private static final Graph.Edge[] GRAPH = {
        new Graph.Edge(0, 1, 10, 30),
        new Graph.Edge(0, 1, 70, 30),
        new Graph.Edge(0, 2, 130, 10),
        new Graph.Edge(1, 2, 60, 30),
        new Graph.Edge(1, 3, 100, 60),
        new Graph.Edge(3, 1, 30, 20)
    };
    private static final int START = 0;
    private static final int END = 2;

    public static void main(String[] args) {
        Graph g = new Graph(GRAPH);
        g.dijkstra(START);
        g.printPath(END);
    }
}

class Graph {
    private final Map<Integer, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges

/** One edge of the graph (only used by Graph constructor) */
    public static class Edge {
        public final int v1, v2;
        public final int busTravelTime;
        public  int busDepartTime;

        public Edge(int v1, int v2, int busDepartTime, int busTravelTime) {
            this.v1 = v1;
            this.v2 = v2;
            this.busTravelTime = busTravelTime;
            this.busDepartTime = busDepartTime;
        }
    }

/** One vertex of the graph, complete with mappings to neighbouring vertices */
public static class Vertex implements Comparable<Vertex> {
    public final int stationNumber;
    public int busTravTime = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
    public Vertex previous = null;
    public final Map<Vertex, Integer> neighbours = new HashMap<>();

    public Vertex(int stationNumber) {
        this.stationNumber = stationNumber;
    }

    private void printPath() {
        if (this == this.previous) {
            System.out.printf("%s", this.stationNumber);
        } else {
            this.previous.printPath();
            System.out.printf(" -> %s(%d)", this.stationNumber, this.busTravTime);
        }
    }

    public int compareTo(Vertex other) {
        return Integer.compare(busTravTime, other.busTravTime);
    }
}


public Graph(Edge[] edges) { //build the graph
    graph = new HashMap<>(edges.length);

    //one pass to find all vertices
    for (Edge e : edges) {
        if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1));
        if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2));
    }

    //another pass to set neighbouring vertices
    for (Edge e : edges) {
        graph.get(e.v1).neighbours.put(graph.get(e.v2), e.busTravelTime);
    }
}

/** Runs dijkstra using a specified source vertex */
public void dijkstra(int startStation) {
    if (!graph.containsKey(startStation)) {
        System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startStation);
        return;
    }
    final Vertex source = graph.get(startStation);
    NavigableSet<Vertex> q = new TreeSet<>();

    // set-up vertices
    for (Vertex v : graph.values()) {
        v.previous = v == source ? source : null;
        v.busTravTime = v == source ? 0 : Integer.MAX_VALUE;
        q.add(v);
    }

    dijkstra(q);
}

    private void dijkstra(final NavigableSet<Vertex> q) {/** dijkstra's algorithm using a binary heap. */
        Vertex u, v;
        while (!q.isEmpty()) {

            u = q.pollFirst(); // vertex with shortest travel time (first iteration will return source)
            if (u.busTravTime == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable

        //look at distances to each neighbour
            for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
                v = a.getKey(); //the neighbour in this iteration

            final int alternateDist = u.busTravTime + a.getValue();
            if (alternateDist < v.busTravTime) { // shorter path to neighbour found
                q.remove(v);
                v.busTravTime = alternateDist;
                v.previous = u;
                q.add(v);
            }
        }
    }
}

    public void printPath(int endStation) {
        graph.get(endStation).printPath();
        System.out.println();
    }
}

Answer 1

Yes, I think this is solvable with a variant of Dijkstra's Algorithm where the backwards pass through the graph calculates the best arrival time at the destination for each graph edge (where that edge can result in arriving at the destination).

First I would introduce a new data type that extends the graph edge to store the arrival time at the goal.

class GoalEdge extends Graph.Edge {

    final int goalArrivalTime;

    GoalEdge(final Graph.Edge edge, final int goalArrivalTime) {
        super(edge.v1, edge.v2, edge.busDepartTime, edge.busTravelTime);
        this.goalArrivalTime = goalArrivalTime;
    }
}

Next I would write the backwards pass over the graph that creates a collection of these new edges that hold the extra information.

class BackwardsPass {

    private final Graph.Edge[] graph;
    private final List<GoalEdge> results = new ArrayList<>();
    private final Queue<Integer> nodesToProcess = new ArrayDeque<>();
    private final Set<Integer> processedNodes = new HashSet<>();

    BackwardsPass(final Graph.Edge[] graph) {
        this.graph = graph;
    }

    Collection<GoalEdge> goalEdgesTo(final int goal) {

        results.clear();
        nodesToProcess.clear();
        processedNodes.clear();

        buildGoalEdgesToGoal(goal);
        buildGoalEdges();

        return results;
    }

    private void buildGoalEdgesToGoal(final int goal) {
        edgesTo(goal)
                .map(edge -> new GoalEdge(edge, edge.busDepartTime + edge.busTravelTime))
                .forEach(results::add);
        queueForProcessingEdgesTo(goal);
        processed(goal);
    }

    private Stream<Graph.Edge> edgesTo(final int destination) {
        return stream(graph).filter(edge -> edge.v2 == destination);
    }

    private void queueForProcessingEdgesTo(final int node) {
        edgesTo(node).forEach(edge -> nodesToProcess.add(edge.v1));
    }

    private void processed(final int node) {
        processedNodes.add(node);
    }

    private void buildGoalEdges() {
        while (!nodesToProcess.isEmpty()) {
            final int nodeToProcess = nodesToProcess.remove();
            if (processedNodes.contains(nodeToProcess)) continue;

            edgesTo(nodeToProcess).forEach(this::buildGoalEdgeFor);
            queueForProcessingEdgesTo(nodeToProcess);
            processed(nodeToProcess);
        }
    }

    private void buildGoalEdgeFor(final Graph.Edge edge) {
        final Optional<GoalEdge> bestOnwardsEdge = bestOnwardEdge(edge);
        if (!bestOnwardsEdge.isPresent()) return;

        final int bestGoalArrivalTime = bestOnwardsEdge.get().goalArrivalTime;
        results.add(new GoalEdge(edge, bestGoalArrivalTime));
    }

    private Optional<GoalEdge> bestOnwardEdge(final Graph.Edge edge) {
        final int arrivalTime = edge.busDepartTime + edge.busTravelTime;
        return results.stream()
                .filter(goalEdge -> goalEdge.v1 == edge.v2)
                .filter(goalEdge -> goalEdge.busDepartTime >= arrivalTime)
                .min((e1, e2) -> e1.goalArrivalTime - e2.goalArrivalTime);
    }
}

Finally, I would write the forward pass over the newly calculated edges like this.

class BusSolver {

    private final Graph.Edge[] graph;

    private Collection<GoalEdge> goalEdges;

    BusSolver(final Graph.Edge... graph) {
        this.graph = graph;
    }

    Route solveFor(final int start, final int startTime, final int goal) {
        goalEdges = new BackwardsPass(graph).goalEdgesTo(goal);
        return findRouteFrom(start, startTime, goal);
    }

    private Route findRouteFrom(final int start,
                                final int startTime,
                                final int goal) {
        int currentNode = start;
        int currentTime = startTime;
        final List<Hop> results = new ArrayList<>();
        while (currentNode != goal) {

            final Optional<GoalEdge> bestGoalEdge = bestGoalEdgeFrom(currentNode, currentTime);
            if (!bestGoalEdge.isPresent()) return null; // TODO - Signal there is no route

            results.add(new Hop(bestGoalEdge.get().busDepartTime, bestGoalEdge.get().v2));
            currentNode = bestGoalEdge.get().v2;
            currentTime = bestGoalEdge.get().busDepartTime + bestGoalEdge.get().busTravelTime;
        }
        return new Route(results);
    }

    private Optional<GoalEdge> bestGoalEdgeFrom(final int currentNode, final int currentTime) {
        return goalEdges.stream()
                .filter(edge -> edge.v1 == currentNode)
                .filter(entry -> entry.busDepartTime >= currentTime)
                .min((x, y) -> x.goalArrivalTime - y.goalArrivalTime);
    }
}

This should give you the correct result for your example which I believe is:

1. Wait till 10 then go from 0 to 1.
2. Wait till 60 then go from 1 to 2.