我正试图解决Sedgewick和Wayne的算法书中的一个问题：单源最短的bitonic路径。
对那些不熟悉问题的人的一些定义：
单调最短路径：单调最短路径是边缘严格增加或严格减小的最短路径。
比特最短路径：从s到t的最短路径，其中存在中间顶点v，使得路径s到v上的边缘的权重严格增加，并且路径上的边缘权重从v到t严格减少。
问题的想法是：
给定边加权有向图，找到从给定源顶点到每个其他顶点（如果存在）的比特最短路径。路径应该简单（没有重复的顶点）。
到目前为止我所拥有的是以下内容：
单调最短路径可以通过以升序放松图中的所有边（以找到上升的单调最短路径）或者以降序放松图中的所有边来计算（以找到下降的单调最短路径） ）。
我预先计算了从源顶点到所有其他顶点的上升单调最短路径（这可以在O（E）中完成，因为它只是一个最短路径树）。
然后我预先计算了所有顶点对的下降单调最短路径，因为任何顶点都可以是中间顶点，任何顶点都可以是目标顶点。这需要O（E * V）时间。
现在，对于从s开始到t结束的每条路径，我可以检查（1）从s到中间顶点v的上升单调最短路径和（2）从v到t的下降单调最短路径的所有组合并选择重量最轻的路径。这将给我一个从s到t的比特最短路径。
但是，有一个问题：我们不能在路径中重复顶点，并且上述想法没有解决这个问题。
解决这个问题的最后一部分的任何想法？任何其他解决问题的想法/方法也是受欢迎的。
（注意：我没有检查你的想法的宏观方案是否真的有用，或者是否有更快的算法。这只能解决重复顶点的问题。）
假设减少路径和增加路径都不包含重复的顶点，重复顶点的唯一机会是，如果顶点存在于“比特”路径的减小和增加部分中。
A --1-- B --3-- C --5-- D --7-- E --7-- D --5-- C --2-- F --1-- Z
在这个例子中，C位于路径的两个部分，E是中间顶点。可以看出，这也意味着从C到E以及从E到C的段在增加和减少路径中必须相同。如果在递减路径中存在不同的（较短的）路径，则当通过该节点路由时，增加的路径也将更短。
这意味着，我们可以简单地切割两个C实例之间的片段，并留下更短的“bitonic”路径。 （或者，我们可以忽略较长的比特路径，因为我们将在以后找到较短的路径，无论如何，当考虑C而不是E作为中间节点时。）
A --1-- B --3-- C --2-- F --1-- Z
这将导致看似奇怪的结果，如A --1-- B --1-- Z，其中两个连续的边具有相同的权重。但是根据你的定义“从s到t的最短路径，其中存在一个中间顶点v，使得路径s到v的边缘的权重严格增加，并且路径上的边缘权重从v到由于A --1-- C和C --1-- Z都是严格单调递增和递减的，所以t仍然是严格减少的“，这应该仍然是一个双向路径。
事实证明，答案看起来比我预期的要简单。
我评论的策略（1）预先计算从源顶点到所有其他顶点的上升单调最短路径，（2）预先计算来自所有顶点对的下降单调最短路径，（3）每个路径从s开始并在t结束，检查从s到中间顶点v的上升单调最短路径的所有组合和从v到t的下降单调最短路径仅在路径可以具有重复顶点时起作用。
当我们寻找简单的路径（没有重复的顶点）时，我们可以（1）按升序放松图中的所有边，然后，在这些相同的路径上，（2）按降序放松图中的所有边。虽然我们按升序放松边缘，但我们确保丢弃仅下降的路径，或者所有边缘具有相同权重的路径（除非恰好有2个相同权重的边缘，请参阅下面对此边缘情况的评论）。当以降序放松边缘时，我们丢弃仅具有上升边缘权重的路径。
这是我提出的算法的一般概念。还涉及一些实现细节：优先级队列用于放松，其中Path对象按最小权重排序。重要的是要考虑具有恰好2个相等权重边的路径的边缘情况（根据问题定义，这是一个比特路径）。
运行时复杂度似乎是O（P lg P），其中P是图中路径的数量。
代码及其依赖项和测试可以在我的GitHub中找到，在这个类中：BitonicShortestPaths.java
我也在这里发布主要代码供参考：
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;
}
}