Single-source shortest bitonic path

Question

I'm trying to solve a question from Sedgewick & Wayne's Algorithms book: the single-source shortest bitonic path.

Some definitions for those that are not familiar with the problem:

Monotonic shortest-path: a monotonic shortest-path is a shortest-path in which the edges are either strictly increasing or strictly decreasing.

Bitonic shortest-path: a shortest-path from s to t in which there is an intermediate vertex v such that the weights of the edges on the path s to v are strictly increasing and the weights of the edges on the path from v to t are strictly decreasing.

The idea of the problem is:

Given an edge-weighted digraph, find a bitonic shortest path from a given source vertex to every other vertex (if one exists). The path should be simple (no repeated vertices).

What I have so far is the following:

A monotonic shortest-path can be computed by relaxing all the edges in the graph in either ascending order (to find an ascending monotonic shortest-path) or relaxing all the edges in the graph in descending order (to find a descending monotonic shortest-path).

I pre-computed the ascending monotonic shortest-path from the source vertex to all other vertices (this can be done in O(E) as it is just one shortest-paths tree).

I then pre-computed the descending monotonic shortest-path from all pairs of vertices, since any vertex can be the intermediate vertex and any vertex can be the target vertex. This is taking O(E * V) time.

Now, for each path starting from s and ending at t, I could check all the combinations of (1) ascending monotonic shortest-path from s to an intermediate vertex v and (2) descending monotonic shortest-path from v to t and select the path with lowest weight. This would give me a bitonic shortest-path from s to t.

However, there is a catch: we cannot have repeated vertices in the path and the above idea does not address this issue.

Any ideas for solving this last part of the problem? Any other ideas/approaches that solve the problem are also welcome.

Answer 1

It turns out that the answer looks simpler than I expected.

The strategy that I commented regarding (1) pre-computing the ascending monotonic shortest-path from the source vertex to all other vertices, (2) pre-computing the descending monotonic shortest-path from all pairs of vertices and, (3) for each path starting from s and ending at t, checking all combinations of ascending monotonic shortest-path from s to an intermediate vertex v and descending monotonic shortest-path from v to t works only when the paths can have repeated vertices.

When we are looking for simple paths (no repeated vertices), we can (1) relax all the edges in the graph in ascending order and then, on these same paths, (2) relax all the edges in the graph in descending order. While we are relaxing edges in ascending order we make sure to discard paths that are only descending, or that have all edges with equal weights (except when there are exactly 2 edges of same weight, see my comment on this edge case below). And when relaxing edges in descending order we discard paths with only ascending edge weights.

This is the general idea of the algorithm I came up with. There are some implementation details involved as well: a priority queue is used for both relaxations with Path objects ordered by smallest weight. It is important to take into account the edge case of a path with exactly 2 edges of equal weight (which, according to the problem definition, is a bitonic path).

The runtime complexity seems to be O(P lg P), where P is the number of paths in the graph.

The code and its dependencies and tests can be found in my GitHub, in this class: BitonicShortestPaths.java

I am also posting the main code here for reference:

public class BitonicSP {

    private Path[] bitonicPathTo;  // bitonic path to vertex

    public BitonicSP(EdgeWeightedDigraph edgeWeightedDigraph, int source) {

        bitonicPathTo = new Path[edgeWeightedDigraph.vertices()];

        // 1- Relax edges in ascending order to get a monotonic increasing shortest path
        Comparator<DirectedEdge> edgesComparator = new Comparator<DirectedEdge>() {
            @Override
            public int compare(DirectedEdge edge1, DirectedEdge edge2) {
                if(edge1.weight() > edge2.weight()) {
                    return -1;
                } else if(edge1.weight() < edge2.weight()) {
                    return 1;
                } else {
                    return 0;
                }
            }
        };

        List<Path> allCurrentPaths = new ArrayList<>();

        relaxAllEdgesInSpecificOrder(edgeWeightedDigraph, source, edgesComparator, allCurrentPaths,true);

        // 2- Relax edges in descending order to get a monotonic decreasing shortest path
        edgesComparator = new Comparator<DirectedEdge>() {
            @Override
            public int compare(DirectedEdge edge1, DirectedEdge edge2) {
                if(edge1.weight() < edge2.weight()) {
                    return -1;
                } else if(edge1.weight() > edge2.weight()) {
                    return 1;
                } else {
                    return 0;
                }
            }
        };

        relaxAllEdgesInSpecificOrder(edgeWeightedDigraph, source, edgesComparator, allCurrentPaths, false);
    }

    private void relaxAllEdgesInSpecificOrder(EdgeWeightedDigraph edgeWeightedDigraph, int source,
                                              Comparator<DirectedEdge> edgesComparator, List<Path> allCurrentPaths,
                                              boolean isAscendingOrder) {

        // Create a map with vertices as keys and sorted outgoing edges as values
        Map<Integer, VertexInformation> verticesInformation = new HashMap<>();
        for(int vertex = 0; vertex < edgeWeightedDigraph.vertices(); vertex++) {
            DirectedEdge[] edges = new DirectedEdge[edgeWeightedDigraph.outdegree(vertex)];

            int edgeIndex = 0;
            for(DirectedEdge edge : edgeWeightedDigraph.adjacent(vertex)) {
                edges[edgeIndex++] = edge;
            }

            Arrays.sort(edges, edgesComparator);

            verticesInformation.put(vertex, new VertexInformation(edges));
        }

        PriorityQueue<Path> priorityQueue = new PriorityQueue<>();

        // If we are relaxing edges for the first time, add the initial paths to the priority queue
        if(isAscendingOrder) {
            VertexInformation sourceVertexInformation = verticesInformation.get(source);
            while (sourceVertexInformation.getEdgeIteratorPosition() < sourceVertexInformation.getEdges().length) {
                DirectedEdge edge = sourceVertexInformation.getEdges()[sourceVertexInformation.getEdgeIteratorPosition()];
                sourceVertexInformation.incrementEdgeIteratorPosition();

                Path path = new Path(edge);
                priorityQueue.offer(path);

                allCurrentPaths.add(path);
            }
        }

        // If we are relaxing edges for the second time, add all existing ascending paths to the priority queue
        if(!allCurrentPaths.isEmpty()) {
            for(Path currentPath : allCurrentPaths) {
                priorityQueue.offer(currentPath);
            }
        }

        while (!priorityQueue.isEmpty()) {
            Path currentShortestPath = priorityQueue.poll();

            DirectedEdge currentEdge = currentShortestPath.directedEdge;

            int nextVertexInPath = currentEdge.to();
            VertexInformation nextVertexInformation = verticesInformation.get(nextVertexInPath);

            // Edge case: a bitonic path consisting of 2 edges of the same weight.
            // s to v with only one edge is strictly increasing, v to t with only one edge is strictly decreasing
            boolean isEdgeCase = false;

            if(currentShortestPath.numberOfEdges() == 2
                    && currentEdge.weight() == currentShortestPath.previousPath.directedEdge.weight()) {
                isEdgeCase = true;
            }

            if((currentShortestPath.isDescending() || isEdgeCase)
                    && (currentShortestPath.weight() < bitonicPathDistTo(nextVertexInPath)
                    || bitonicPathTo[nextVertexInPath] == null)) {
                bitonicPathTo[nextVertexInPath] = currentShortestPath;
            }

            double weightInPreviousEdge = currentEdge.weight();

            while (nextVertexInformation.getEdgeIteratorPosition() < nextVertexInformation.getEdges().length) {
                DirectedEdge edge =
                        verticesInformation.get(nextVertexInPath).getEdges()[nextVertexInformation.getEdgeIteratorPosition()];

                boolean isEdgeInEdgeCase = currentShortestPath.numberOfEdges() == 1
                        && edge.weight() == weightInPreviousEdge;

                if(!isEdgeInEdgeCase && ((isAscendingOrder && edge.weight() <= weightInPreviousEdge)
                        || (!isAscendingOrder && edge.weight() >= weightInPreviousEdge))) {
                    break;
                }

                nextVertexInformation.incrementEdgeIteratorPosition();

                Path path = new Path(currentShortestPath, edge);
                priorityQueue.offer(path);

                // If we are relaxing edges for the first time, store the ascending paths so they can be further
                // relaxed when computing the descending paths on the second relaxation
                if(isAscendingOrder) {
                    allCurrentPaths.add(path);
                }
            }
        }
    }

    public double bitonicPathDistTo(int vertex) {
        if(hasBitonicPathTo(vertex)) {
            return bitonicPathTo[vertex].weight();
        } else {
            return Double.POSITIVE_INFINITY;
        }
    }

    public boolean hasBitonicPathTo(int vertex) {
        return bitonicPathTo[vertex] != null;
    }

    public Iterable<DirectedEdge> bitonicPathTo(int vertex) {

        if(!hasBitonicPathTo(vertex)) {
            return null;
        }

        return bitonicPathTo[vertex].getPath();
    }
}

public class Path implements Comparable<Path> {
    private Path previousPath;
    private DirectedEdge directedEdge;
    private double weight;
    private boolean isDescending;
    private int numberOfEdges;

    Path(DirectedEdge directedEdge) {
        this.directedEdge = directedEdge;
        weight = directedEdge.weight();

        numberOfEdges = 1;
    }

    Path(Path previousPath, DirectedEdge directedEdge) {
        this(directedEdge);
        this.previousPath = previousPath;

        weight += previousPath.weight();
        numberOfEdges += previousPath.numberOfEdges;

        if(previousPath != null && previousPath.directedEdge.weight() > directedEdge.weight()) {
            isDescending = true;
        }
    }

    public double weight() {
        return weight;
    }

    public boolean isDescending() {
        return isDescending;
    }

    public int numberOfEdges() {
        return numberOfEdges;
    }

    public Iterable<DirectedEdge> getPath() {
        LinkedList<DirectedEdge> path = new LinkedList<>();

        Path iterator = previousPath;

        while (iterator != null && iterator.directedEdge != null) {
            path.addFirst(iterator.directedEdge);

            iterator = iterator.previousPath;
        }
        path.add(directedEdge);

        return path;
    }

    @Override
    public int compareTo(Path other) {
        if(this.weight < other.weight) {
            return -1;
        } else if(this.weight > other.weight) {
            return 1;
        } else {
            return 0;
        }
    }
}

public class VertexInformation {

    private DirectedEdge[] edges;
    private int edgeIteratorPosition;

    VertexInformation(DirectedEdge[] edges) {
        this.edges = edges;
        edgeIteratorPosition = 0;
    }

    public void incrementEdgeIteratorPosition() {
        edgeIteratorPosition++;
    }

    public DirectedEdge[] getEdges() {
        return edges;
    }

    public int getEdgeIteratorPosition() {
        return edgeIteratorPosition;
    }
}

Answer 2

(Note: I did not check whether the grand scheme of your idea really holds up, or whether there might be a faster algorithm. This solely addresses the issue of repeated vertices.)

Assuming that neither the decreasing- nor the increasing paths contain repeated vertices, the only chance for repeated vertices is if a vertex exists in both, the decreasing and the increasing portion of the "bitonic" path.

A --1-- B --3-- C --5-- D --7-- E --7-- D --5-- C --2-- F --1-- Z

In this example, C is in both parts of the path, with E being the intermediate vertex. As can be seen, this also means that the segment from C to E and from E to C have to be the same in both the increasing and the decreasing path. If there was a different (shorter) path in the decreasing path, then the increasing path would also be shorter when routed via that node.

This means, that we can simply cut the segment between the two instance of C and are left with an even shorter "bitonic" path. (Or, we can just ignore the longer bitonic path, as we will find the shorter one later, anyway, when considering C instead of E as the intermediate node.)

A --1-- B --3-- C --2-- F --1-- Z

This would result in seemingly weird results like A --1-- B --1-- Z, where two consecutive edges have the same weight. But according to your definition "a shortest-path from s to t in which there is an intermediate vertex v such that the weights of the edges on the path s to v are strictly increasing and the weights of the edges on the path from v to t are strictly decreasing", this should still be a bitonic path, since both A --1-- C as well as C --1-- Z are strictly monotonic increasing and decreasing, respectively.