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<>();

        final Map<Integer, SPTEntry> bestWeightMapByNode = new HashMap<>();
        bestWeightMapTo.forEach((IntObjectPredicate<SPTEntry>) (key, value) -> {
            bestWeightMapByNode.put(value.adjNode, value);
            return true;
        });

        bestWeightMapFrom.forEach((IntObjectPredicate<SPTEntry>) (wurst, fromSPTEntry) -> {
            SPTEntry toSPTEntry = bestWeightMapByNode.get(fromSPTEntry.adjNode);
            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;
            }
            assert fromSPTEntry.adjNode == toSPTEntry.adjNode;
            PotentialAlternativeInfo potentialAlternativeInfo = new PotentialAlternativeInfo();
            potentialAlternativeInfo.v = fromSPTEntry.adjNode;
            potentialAlternativeInfo.edgeIn = getIncomingEdge(fromSPTEntry);
            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;
            int tailSv = potentialAlternativeInfo.edgeIn;

            // Okay, now we want the s -> v -> t shortest via-path, so we route s -> v and v -> t
            // and glue them together.
            DijkstraBidirectionEdgeCHNoSOD svRouter = new DijkstraBidirectionEdgeCHNoSOD(graph);
            final Path suvPath = svRouter.calcPath(s, v, ANY_EDGE, tailSv);
            extraVisitedNodes += svRouter.getVisitedNodes();

            int u = graph.getBaseGraph().getEdgeIteratorState(tailSv, v).getBaseNode();

            DijkstraBidirectionEdgeCHNoSOD vtRouter = new DijkstraBidirectionEdgeCHNoSOD(graph);
            final Path uvtPath = vtRouter.calcPath(u, t, tailSv, ANY_EDGE);
            Path path = concat(graph.getBaseGraph(), suvPath, uvtPath);
            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 = suvPath.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", 4);
        hints.putObject("alternative_route.local_optimality_factor", 0.5);
        hints.putObject("alternative_route.max_paths", 4);
        RoutingCHGraph routingCHGraph = prepareCH(g);
        AlternativeRouteEdgeCH altDijkstra = new AlternativeRouteEdgeCH(routingCHGraph, hints);
        List<AlternativeRouteEdgeCH.AlternativeInfo> pathInfos = altDijkstra.calcAlternatives(5, 10);
        assertEquals(2, pathInfos.size());
        assertEquals(IntArrayList.from(5, 6, 7, 8, 4, 10), pathInfos.get(0).path.calcNodes());
        assertEquals(IntArrayList.from(5, 1, 9, 2, 3, 4, 10), pathInfos.get(1).path.calcNodes());
        // 3 -> 4 -> 11 is forbidden
        // 6 -> 3 -> 4 is forbidden
    }