基于DFS的路径寻路中如何排除首次出发前的等待时间？

你的当前方法完全可行 #

你通过记录firstDepartureTime，最终用lastArrivalTime - firstDepartureTime计算总耗时的思路，完美解决了忽略初始等待时间的需求：

• 这个计算方式直接覆盖了从首个班次出发到最终到达的全部时间，自然排除了用户指定出发时间到首个班次之间的空闲等待
• 换乘时的等待时间已经包含在各段行程的间隔中，最终总时间会自动统计这部分时长，和你期望的结果一致

比如你举的例子：

departureTime = 06:00（360分钟），首个班次13:00出发，后续班次15:00出发
总等待时间仅统计15:00-13:00=2小时，总耗时为最终到达时间减去13:00，完全符合预期

不过你的代码里存在冗余逻辑：当前代码中会累加additionalTime到currentPath.totalTime，但最后在到达目标城市时又重新计算了totalTime，这部分中间累加完全可以去掉，避免不必要的状态维护。

更简洁的优化方案 #

核心思路不变，简化中间状态的维护：

1. 去掉中间的totalTime累加：不需要在遍历过程中维护totalTime，只在找到目标城市时，用「最终到达时间 - 首个班次出发时间」直接计算总耗时即可
2. 保持初始等待的判断逻辑：在添加第一个班次时，将firstDepartureTime设为该班次的出发时间，同时跳过初始等待时间的统计（waiting=0）

优化后的代码片段 #

修改DFS中的totalTime处理部分，去掉中间累加：

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 = !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;
        }

        // 去掉additionalTime的计算和totalTime的累加
        currentPath.edges.add(edge);
        currentPath.totalCost += additionalCost;
        currentPath.transferCount += additionalTransfers;

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

        // 回溯时也不需要恢复totalTime
        currentPath.edges.remove(currentPath.edges.size() - 1);
        currentPath.totalCost -= additionalCost;
        currentPath.transferCount -= additionalTransfers;
    }

    visited.remove(current);
}

逻辑验证 #

针对你的示例场景：

• 用户指定出发时间：06:00（360分钟）
• 首个班次出发时间：13:00（780分钟），到达时间14:00（840分钟）
• 换乘班次出发时间：15:00（900分钟），到达时间16:00（960分钟）
• 最终总耗时=960-780=180分钟（3小时），其中包含换乘等待60分钟+两段行程各60分钟，完全排除了06:00到13:00的空闲时间，符合需求

内容的提问来源于stack exchange，提问作者SP222