DijkstraRouter.java (2674B) download
1package osm.routing.strategy;
2
3import java.util.Map;
4import java.util.PriorityQueue;
5import java.util.Queue;
6
7import osm.geo.Point;
8import osm.routing.RoutingEdge;
9import osm.routing.RoutingGraph;
10import osm.routing.RoutingNode;
11import osm.routing.RoutingStrategy;
12import 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 */
21public 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}