persolijn

an efficient router for busses
Log | Files | Refs

DijkstraRouter.java (2674B)

      1 package osm.routing.strategy;
      2 
      3 import java.util.Map;
      4 import java.util.PriorityQueue;
      5 import java.util.Queue;
      6 
      7 import osm.geo.Point;
      8 import osm.routing.RoutingEdge;
      9 import osm.routing.RoutingGraph;
     10 import osm.routing.RoutingNode;
     11 import osm.routing.RoutingStrategy;
     12 import osm.routing.RoutingGraph.Route;
     13 
     14 /**
     15  * A base class for implementing routing algorithms between two points on a
     16  * graph using Dijkstra's algorithm.
     17  *
     18  * @param <N> The type of nodes in the graph.
     19  * @param <E> The type of edges in the graph.
     20  */
     21 public class DijkstraRouter<N extends RoutingNode<N>, E extends RoutingEdge<N>> implements RoutingStrategy<N, E> {
     22 
     23     /**
     24      * Finds the optimal route between the start node and a collection of target
     25      * nodes using Dijkstra's algorithm.
     26      *
     27      * @param graph   The graph on which the routing is performed.
     28      * @param targets The target nodes and their distances.
     29      * @param start   The starting node.
     30      * @param offset  The offset value.
     31      * @return A {@link Route} representing the optimal route from the start to a
     32      *         target
     33      *         node, or null if no route is found.
     34      */
     35     @Override
     36     public Route<N> route(RoutingGraph<N, E> graph, Map<N, Long> targets, N start, long offset) {
     37         Queue<N> openNodes = new PriorityQueue<>(RoutingNode.heuristicComparator());
     38 
     39         double bestProgress = 0;
     40 
     41         openNodes.add(start);
     42 
     43         start.setScore(0L);
     44         start.setHeuristicScore(graph.getHeuristic(targets, start));
     45 
     46         while (!openNodes.isEmpty()) {
     47             N current = openNodes.poll();
     48 
     49             double currentProgress = graph.getProgress(targets, start, offset, current);
     50             if (currentProgress > bestProgress)
     51                 graph.onProgress(bestProgress = currentProgress, start, targets.keySet());
     52 
     53             if (graph.isTarget(targets, current)) {
     54                 N[] history = graph.getHistory(current);
     55                 return new Route<>(current, history, Point.distance(history));
     56             }
     57 
     58             graph.forNeighbor(current, edge -> {
     59                 N next = edge.getDestination();
     60                 if (next.equals(current))
     61                     return;
     62 
     63                 long totalWeight = current.getScore() + graph.getCost(current, edge);
     64 
     65                 if (totalWeight >= next.getScore())
     66                     return;
     67 
     68                 next.setParent(current);
     69                 next.setScore(totalWeight);
     70                 next.setHeuristicScore(totalWeight + graph.getHeuristic(targets, next));
     71 
     72                 if (!openNodes.contains(next))
     73                     openNodes.add(next);
     74             });
     75         }
     76         return null;
     77     }
     78 }