Trova la connessione più veloce a un certo punto

Quello che sto cercando di implementare è un programma che sta cercando la connessione più veloce da una stazione all'altra in un dato momento della giornata.

Ho un numero di stazioni n e un numero m di linee che collegano queste stazioni. Ogni riga ha (departStation, arrivalStation, busDepartTime, busTravelTime) .

Quando voglio cercare una connessione dalla stazione A a B avrò l'input (from, to, myDepartTime) .

Se ho iniziato a pensare correttamente, le stazioni saranno Vertex e ogni linea sarà un vantaggio. Volevo utilizzare l'algoritmo di Dijkstra per implementarlo, ma troverò il tempo di viaggio più breve di un autobus (vedi esempio 1).

Cosa devo cambiare nel codice per ottenere il risultato desiderato come nell'esempio 1? C'è qualche altro algoritmo che posso usare? Forse uno migliore? O solo qualche consiglio?

Devo sapere se sono sulla buona strada. Sto solo cercando di creare un semplice programma da riga di comando, niente di complesso.

Sto pensando di calcolare il tempo in cui devo aspettare che l'autobus parte e la durata totale del viaggio e quindi scegliere il più breve da tutti. L'unico problema è che non capisco davvero come posso implementarlo.

Esempio 1:

4 stazioni: 0, 1, 2, 3

4 linee (connessioni)

Nota: i tempi di partenza sono indicati in minuti dall'inizio del giorno (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)

Ora devo passare da 0 a 2 a 00 ( 0, 2, 00 ) L'algoritmo di Dijkstra che ho restituirà il busTravelTime più breve che è 30 e stamperà il percorso 0 - > 2(10) . È fantastico, ma non è buono perché devo aspettare 130 minuti. Quello che sarà bello è ottenere il percorso 0 -> 1(30) -> 2(60) perché il bus parte a 30 e devo aspettare solo 10 minuti.

Ecco il codice:

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();
    }
}