List<AlternativeInfo> calcAlternatives(final int s, final int t) {
        // First, do a regular bidirectional route search
        checkAlreadyRun();
        init(s, 0, t, 0);
        runAlgo();
        final Path bestPath = extractPath();
        if (!bestPath.isFound()) {
            return Collections.emptyList();
        }

        alternatives.add(new AlternativeInfo(bestPath, 0));

        final ArrayList<PotentialAlternativeInfo> potentialAlternativeInfos = new ArrayList<>();

        bestWeightMapFrom.forEach((IntObjectPredicate<SPTEntry>) (v, fromSPTEntry) -> {
            SPTEntry toSPTEntry = bestWeightMapTo.get(v);
            if (toSPTEntry == null)
                return true;

            if (fromSPTEntry.getWeightOfVisitedPath() + toSPTEntry.getWeightOfVisitedPath() > bestPath.getWeight() * maxWeightFactor)
                return true;

            // This gives us a path s -> v -> t, but since we are using contraction hierarchies,
            // s -> v and v -> t need not be shortest paths. In fact, they can sometimes be pretty strange.
            // We still use this preliminary path to filter for shared path length with other alternatives,
            // so we don't have to work so much.
            Path preliminaryRoute = createPathExtractor().extract(fromSPTEntry, toSPTEntry, fromSPTEntry.getWeightOfVisitedPath() + toSPTEntry.getWeightOfVisitedPath());
            double preliminaryShare = calculateShare(preliminaryRoute);
            if (preliminaryShare > maxShareFactor) {
                return true;
            }
            PotentialAlternativeInfo potentialAlternativeInfo = new PotentialAlternativeInfo();
            potentialAlternativeInfo.v = v;
            potentialAlternativeInfo.weight = 2 * (fromSPTEntry.getWeightOfVisitedPath() + toSPTEntry.getWeightOfVisitedPath()) + preliminaryShare;
            potentialAlternativeInfos.add(potentialAlternativeInfo);
            return true;
        });

        potentialAlternativeInfos.sort(Comparator.comparingDouble(o -> o.weight));

        for (PotentialAlternativeInfo potentialAlternativeInfo : potentialAlternativeInfos) {
            int v = potentialAlternativeInfo.v;

            // Okay, now we want the s -> v -> t shortest via-path, so we route s -> v and v -> t
            // and glue them together.
            DijkstraBidirectionCH svRouter = new DijkstraBidirectionCH(graph);
            svRouter.setPathExtractorSupplier(this::createPathExtractor);
            final Path svPath = svRouter.calcPath(s, v);
            extraVisitedNodes += svRouter.getVisitedNodes();

            DijkstraBidirectionCH vtRouter = new DijkstraBidirectionCH(graph);
            vtRouter.setPathExtractorSupplier(this::createPathExtractor);
            final Path vtPath = vtRouter.calcPath(v, t);
            Path path = concat(graph.getBaseGraph(), svPath, vtPath);
            extraVisitedNodes += vtRouter.getVisitedNodes();

            double sharedDistanceWithShortest = sharedDistanceWithShortest(path);
            double detourLength = path.getDistance() - sharedDistanceWithShortest;
            double directLength = bestPath.getDistance() - sharedDistanceWithShortest;
            if (detourLength > directLength * maxWeightFactor) {
                continue;
            }

            double share = calculateShare(path);
            if (share > maxShareFactor) {
                continue;
            }

            // This is the final test we need: Discard paths that are not "locally shortest" around v.
            // So move a couple of nodes to the left and right from v on our path,
            // route, and check if v is on the shortest path.
            final IntIndexedContainer svNodes = svPath.calcNodes();
            int vIndex = svNodes.size() - 1;
            if (!tTest(path, vIndex))
                continue;

            alternatives.add(new AlternativeInfo(path, share));
            if (alternatives.size() >= maxPaths)
                break;
        }
        return alternatives;
    }
@Test
    public void testCalcAlternatives() {
        BaseGraph g = createTestGraph(em);
        PMap hints = new PMap();
        hints.putObject("alternative_route.max_weight_factor", 2.3);
        hints.putObject("alternative_route.local_optimality_factor", 0.5);
        hints.putObject("alternative_route.max_paths", 4);
        RoutingCHGraph routingCHGraph = prepareCH(g);
        AlternativeRouteCH altDijkstra = new AlternativeRouteCH(routingCHGraph, hints);
        List<AlternativeRouteCH.AlternativeInfo> pathInfos = altDijkstra.calcAlternatives(5, 10);
        assertEquals(3, pathInfos.size());
        // 4 -> 11 -> 12 is shorter than 4 -> 10 -> 12 (11 is an admissible via node), BUT
        // 4 -> 11 -> 12 -> 10 is too long compared to 4 -> 10
    }