@Test public void noPath() { graph = new AdjacencyListsGraph<>(of(A, B, C, D), of(new TestEdge(A, B, 1), new TestEdge(B, A, 1), new TestEdge(C, D, 1), new TestEdge(D, C, 1))); GraphPathSearch<TestVertex, TestEdge> gs = graphSearch(); Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weight, 1).paths(); printPaths(paths); assertEquals("incorrect paths count", 1, paths.size()); assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1); paths = gs.search(graph, A, D, weight, 1).paths(); printPaths(paths); assertEquals("incorrect paths count", 0, paths.size()); paths = gs.search(graph, A, null, weight, 1).paths(); printPaths(paths); assertEquals("incorrect paths count", 1, paths.size()); assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1); }
@Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, false); if (graph.getEdges().isEmpty()) { result.buildPaths(); return result; } Heap<V> minQueue = createMinQueue(graph.getVertexes(), new PathCostComparator(result)); while (!minQueue.isEmpty()) { V nearest = minQueue.extractExtreme(); if (nearest.equals(dst)) { break; } double cost = result.cost(nearest); if (cost < Double.MAX_VALUE) { for (E e : graph.getEdgesFrom(nearest)) { result.relaxEdge(e, cost, weight, true); } } minQueue.heapify(); } result.buildPaths(); return result; }
DijkstraGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, false); if (graph.getEdges().isEmpty()) { result.buildPaths(); return result; } Heap<V> minQueue = createMinQueue(graph.getVertexes(), new PathCostComparator(result)); while (!minQueue.isEmpty()) { V nearest = minQueue.extractExtreme(); if (nearest.equals(dst)) { break; } double cost = result.cost(nearest); if (cost < Double.MAX_VALUE) { for (E e : graph.getEdgesFrom(nearest)) { result.relaxEdge(e, cost, weight, true); } } minQueue.heapify(); } result.buildPaths(); return result; } }
DijkstraGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, false); if (graph.getEdges().isEmpty()) { result.buildPaths(); return result; } Heap<V> minQueue = createMinQueue(graph.getVertexes(), new PathCostComparator(result)); while (!minQueue.isEmpty()) { V nearest = minQueue.extractExtreme(); if (nearest.equals(dst)) { break; } double cost = result.cost(nearest); if (cost < Double.MAX_VALUE) { for (E e : graph.getEdgesFrom(nearest)) { result.relaxEdge(e, cost, weight, true); } } minQueue.heapify(); } result.buildPaths(); return result; }  }
DijkstraGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, false); if (graph.getEdges().isEmpty()) { result.buildPaths(); return result; } Heap<V> minQueue = createMinQueue(graph.getVertexes(), new PathCostComparator(result)); while (!minQueue.isEmpty()) { V nearest = minQueue.extractExtreme(); if (nearest.equals(dst)) { break; } double cost = result.cost(nearest); if (cost < Double.MAX_VALUE) { for (E e : graph.getEdgesFrom(nearest)) { result.relaxEdge(e, cost, weight, true); } } minQueue.heapify(); } result.buildPaths(); return result; }  @Override Result<V, E> search(Graph<V, E> graph, V src, V dst,
                               EdgeWeight<V, E> weight, int maxPaths); }
DijkstraGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, false); if (graph.getEdges().isEmpty()) { result.buildPaths(); return result; } Heap<V> minQueue = createMinQueue(graph.getVertexes(), new PathCostComparator(result)); while (!minQueue.isEmpty()) { V nearest = minQueue.extractExtreme(); if (nearest.equals(dst)) { break; } double cost = result.cost(nearest); if (cost < Double.MAX_VALUE) { for (E e : graph.getEdgesFrom(nearest)) { result.relaxEdge(e, cost, weight, true); } } minQueue.heapify(); } result.buildPaths(); return result; }  @Override Result<V, E> search(Graph<V, E> graph, V src, V dst,
                               EdgeWeight<V, E> weight, int maxPaths);  }