class AlternativeRouteCH extends DijkstraBidirectionCHNoSOD {

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

        final List<AlternativeInfo> alternatives = new ArrayList<>();
        alternatives.add(new AlternativeInfo(bestPath, 0));
        final double maxWeight = maxWeightFactor * bestPath.getWeight();

        bestWeightMapFrom.forEach(new IntObjectPredicate<SPTEntry>() {
            @Override
            public boolean apply(final int v, final SPTEntry fromSPTEntry) {
                SPTEntry toSPTEntry = bestWeightMapTo.get(v);
                if (toSPTEntry == null)
                    return true;

                // Filter alternatives that are too long
                if (fromSPTEntry.getWeightOfVisitedPath() + toSPTEntry.getWeightOfVisitedPath() > maxWeight)
                    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(graph).extract(fromSPTEntry, toSPTEntry, fromSPTEntry.getWeightOfVisitedPath() + toSPTEntry.getWeightOfVisitedPath());
                double preliminaryShare = calculateShare(preliminaryRoute);
                if (preliminaryShare > maxShareFactor) {
                    return true;
                }

                // Okay, now we want the s -> v -> t shortest via-path, so we route s -> v and v -> t
                // and glue them together.
                DijkstraBidirectionCHNoSOD svRouter = new DijkstraBidirectionCHNoSOD(graph);
                final Path svPath = svRouter.calcPath(s, v);
                DijkstraBidirectionCHNoSOD vtRouter = new DijkstraBidirectionCHNoSOD(graph);
                final Path vtPath = vtRouter.calcPath(v, t);
                Path path = concat(graph.getGraph().getBaseGraph(), svPath, vtPath);

                // And calculate the share again, because this can be totally different.
                // The first filter is a good heuristic, but we still need this one.
                double share = calculateShare(path);
                if (share > maxShareFactor) {
                    return true;
                }

                // 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))
                    return true;

                alternatives.add(new AlternativeInfo(path, share));
                return true;
            }

            private double calculateShare(final Path path) {
                double sharedDistance = 0.0;
                List<EdgeIteratorState> edges = path.calcEdges();
                for (EdgeIteratorState edge : edges) {
                    if (nodesInCurrentAlternativeSetContains(edge.getBaseNode()) && nodesInCurrentAlternativeSetContains(edge.getAdjNode())) {
                        sharedDistance += edge.getDistance();
                    }
                }
                return sharedDistance / path.getDistance();
            }

            private boolean nodesInCurrentAlternativeSetContains(int v) {
                for (AlternativeInfo alternative : alternatives) {
                    if (alternative.nodes.contains(v)) {
                        return true;
                    }
                }
                return false;
            }

            private boolean tTest(Path path, int vIndex) {
                if (path.getEdgeCount() == 0) return true;
                int fromNode = getPreviousNodeTMetersAway(path, vIndex);
                int toNode = getNextNodeTMetersAway(path, vIndex);
                DijkstraBidirectionCHNoSOD tRouter = new DijkstraBidirectionCHNoSOD(graph);
                Path tPath = tRouter.calcPath(fromNode, toNode);
                IntIndexedContainer tNodes = tPath.calcNodes();
                return tNodes.contains(path.calcNodes().get(vIndex));
            }

            private int getPreviousNodeTMetersAway(Path path, int vIndex) {
                List<EdgeIteratorState> edges = path.calcEdges();
                double distance = 0.0;
                int i = vIndex;
                while (i > 0 && distance < T) {
                    distance += edges.get(i - 1).getDistance();
                    i--;
                }
                return edges.get(i).getBaseNode();
            }

            private int getNextNodeTMetersAway(Path path, int vIndex) {
                List<EdgeIteratorState> edges = path.calcEdges();
                double distance = 0.0;
                int i = vIndex;
                while (i < edges.size() - 1 && distance < T) {
                    distance += edges.get(i).getDistance();
                    i++;
                }
                return edges.get(i - 1).getAdjNode();
            }

        });
        Collections.sort(alternatives, new Comparator<AlternativeInfo>() {
            @Override
            public int compare(AlternativeInfo o1, AlternativeInfo o2) {
                return Double.compare(o1.path.getWeight(), o2.path.getWeight());
            }
        });
        return alternatives;
    }

    public  AlternativeRouteCH(RoutingCHGraph graph);

}