Avoid counting waiting time before the first departure in DFS-based pathfinding graph

Question

I have a graph-based travel system where each city has two stations: a bus station and a train station. Each station is represented as a node (Node), and each connection/departure is represented as an edge (Edge) that may contain departure time, duration, cost, and type (e.g. bus or train). I use DFS to find all possible paths from the starting node to the destination city.

Here is the problem:

I specify a departureTime, for example 06:00 (converted to minutes), which is passed as the starting time to DFS. This is supposed to simulate the earliest time the traveler can start.

Now, let's say the first available departure is at 13:00. I don’t want the algorithm to count the time from 06:00 to 13:00 as waiting time. I only want waiting time between transfers (e.g. when changing from one departure to another).

Is there a clean way to handle this in DFS? Here's what I currently do:

When adding the first departure to the path, I store its time as firstDepartureTime.

Then I compute the total time as lastArrivalTime - firstDepartureTime.

Is this a good approach? Or is there a better way to ignore the initial idle time and only calculate waiting time between connections?

If I specify:

departureTime = timeStringToMinutes("06:00");

And the first edge (departure) available is at 13:00, and then another connection at 15:00, I want:

total waiting time = 15:00 - 13:00 = 2 hours (only this counts),

NOT 13:00 - 06:00 + 2 hours.

private static void dfs(Node current, String targetCity, Path currentPath, List<Path> allPaths, Set<Node> visited, Node previousNode, int previousArrivalTime) {
    if (current.getCityName().equals(targetCity)) {
        Path newPath = new Path(currentPath);
        if (newPath.firstDepartureTime != -1) {
            newPath.totalTime = previousArrivalTime - newPath.firstDepartureTime;
        }
        allPaths.add(newPath);
        return;
    }

    visited.add(current);

    for (Edge edge : current.neighbors) {
        Node next = edge.getDestinationStation();

        if (visited.contains(next))
            continue;

        int additionalCost = (edge.getDeparture() != null) ? edge.getDeparture().getPrice() : 0;
        int duration = (edge.getDeparture() != null) ? edge.getDeparture().getDuration() : edge.getWeight();

        int additionalTransfers = 0;
        if (previousNode != null) {
            boolean cityChanged = previousNode != null
                    && !current.getCityName().equals(targetCity)
                    && !current.getCityName().equals(previousNode.getCityName());

            if (cityChanged) {
                additionalTransfers = 1;
            }
        }

        int waiting = 0;
        int nextArrivalTime;

        if (edge.getDeparture() != null) {
            int edgeDepartureTime = timeStringToMinutes(edge.getDeparture().getDepartureTime());
            int minTransferTime = edge.getDeparture().getMinimalWaitingTime();

            if (edgeDepartureTime < previousArrivalTime + minTransferTime)
                continue;

            if (currentPath.edges.isEmpty()) {
                currentPath.firstDepartureTime = edgeDepartureTime;
                waiting = 0;
            } else {
                waiting = edgeDepartureTime - previousArrivalTime;
            }

            nextArrivalTime = edgeDepartureTime + edge.getDeparture().getDuration();
        } else {
            nextArrivalTime = previousArrivalTime + duration;
        }

        int additionalTime = duration + waiting;

        currentPath.edges.add(edge);
        currentPath.totalCost += additionalCost;
        currentPath.totalTime += additionalTime;
        currentPath.transferCount += additionalTransfers;

        dfs(next, targetCity, currentPath, allPaths, visited, current, nextArrivalTime);

        currentPath.edges.remove(currentPath.edges.size() - 1);
        currentPath.totalCost -= additionalCost;
        currentPath.totalTime -= additionalTime;
        currentPath.transferCount -= additionalTransfers;
    }

    visited.remove(current);
}

I am not sure to understand what are you trying to optimize here. If you want to find the shortest total travel time (including waiting time), why not use Dijkstra? (Note that Dijkstra doesn't necessarily need the total cost of reaching node B via node via edge (A,B) to be f(A,B)=λ(A)+val((A,B)) (used to test if f(A,B)<λ(B) then λ(B)=f(A,B)). In 99% of Dijkstra algorithm taught, that f(A,B) is λ(A)+val(A,B). But in reality any f(A,B) such as f(A,B)>f(A) is sufficient so that DIjkstra can be proven to find the optimal solution. — chrslg
– chrslg, Commented Jul 30 at 13:25
So, in your case, if what you want is to compute duration including waiting time, then f(A,B) = λ(A) + arrival(A,B) if departure(A)>λ(A) else ∞ would find best arrival time λ. — chrslg
– chrslg, Commented Jul 30 at 13:27
And you can of course, use many variant of f (for waiting time, cost, etc, etc). Anything, as long as what you compute (λ: cost, distance, time, waiting time, arrival time, ...) has an order (you can always tel λ₁<λ₂ or λ₁≥λ₂), and is such as f(A,B) > λ(A) — chrslg
– chrslg, Commented Jul 30 at 13:29
Do you want to take into account all possible departures from the start station? Like also those that go in opposite direction, ...etc? What is holding you back to find the very first departure, and take the difference from the initial time, and subtract that at the very end, when you have the outcome? — trincot
– trincot, Commented Jul 30 at 13:37

Brian Stinar · Accepted Answer · 2025-08-17 02:42:21Z

0

Have you considered using virtual nodes with zero weighted edges to represent state transitions from your 0600 to your 1300 states at the same station? All nodes could have zero-weighted edges to virtual nodes at the same location, but with later times. I believe this would allow you to continue to use DFS with your existing edge.getWeight() call.

answered Aug 17 at 2:42

Brian Stinar

1,1071 gold badge15 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Avoid counting waiting time before the first departure in DFS-based pathfinding graph

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related