单源最短双子路径
Single-source shortest bitonic path
我正在尝试解决 Sedgewick & Wayne 的算法书中的一个问题：单源最短双调路径。
一些不熟悉问题的定义：
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.
题目思路是：
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).
到目前为止我有以下内容：
单调最短路径可以通过按升序放宽图中的所有边（找到升序单调最短路径）或按降序放宽图中的所有边（找到降序单调最短路径）。
我预先计算了从源顶点到所有其他顶点的升序单调最短路径（这可以在 O(E) 中完成，因为它只是一棵最短路径树）。
然后我预先计算了所有顶点对的降序单调最短路径，因为任何顶点都可以是中间顶点，任何顶点都可以是目标顶点。这需要 O(E * V) 时间。
现在，对于从 s 开始到 t 结束的每条路径，我可以检查 (1) 从 s 到中间顶点 v 的上升单调最短路径和 (2) 从 s 开始的下降单调最短路径的所有组合v 到 t 和 select 权重最低的路径。
这会给我一条从 s 到 t 的双调最短路径。
但是，有一个问题：我们不能在路径中有重复的顶点，并且上述想法没有解决这个问题。
对于解决问题的最后一部分有什么想法吗？
也欢迎解决问题的任何其他ideas/approaches。
（注意：我没有检查你的想法的宏伟计划是否真的成立，或者是否有更快的算法。这仅解决重复顶点的问题。）
假设递减路径和递增路径都不包含重复顶点，重复顶点的唯一机会是如果一个顶点同时存在于"bitonic"路径的递减和递增部分。
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，其中两条连续的边具有相同的权重。但是根据你的定义 "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"，这应该仍然是双调路径，因为 A --1-- C 和 C --1-- Z 分别是严格单调递增和单调递减。
原来答案看起来比我想象的要简单
我评论的策略是 (1) 预计算从源顶点到所有其他顶点的单调升序最短路径，(2) 预计算所有顶点对的降序单调最短路径，以及, (3) 对于从 s 开始到 t 结束的每条路径，检查从 s 到中间顶点 v 的升序单调最短路径和从 v 到 t 的降序单调最短路径的所有组合仅在路径可以具有重复顶点时有效.
当我们寻找简单的路径（没有重复的顶点）时，我们可以 (1) 按升序松弛图中的所有边，然后，在这些相同的路径上，(2) 松弛图中的所有边图降序排列。当我们按升序松弛边时，我们确保丢弃仅下降的路径，或者所有边具有相同权重的路径（除非恰好有 2 个边具有相同的权重，请参阅下面我对这个边缘情况的评论）。当按降序松弛边时，我们丢弃只有上升边权重的路径。
这是我想出的算法的大概思路。还涉及一些实现细节：优先级队列用于两个放宽，路径对象按最小权重排序。重要的是要考虑具有恰好 2 个权重相等的边的路径的边缘情况（根据问题定义，这是一条双调路径）。
运行时复杂度似乎是 O(P lg P)，其中 P 是图中路径的数量。
代码及其依赖和测试可以在我的GitHub中找到，在这个class中：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;
}
}
我正在尝试解决 Sedgewick & Wayne 的算法书中的一个问题：单源最短双调路径。
一些不熟悉问题的定义：
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.
题目思路是：
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).
到目前为止我有以下内容：
单调最短路径可以通过按升序放宽图中的所有边（找到升序单调最短路径）或按降序放宽图中的所有边（找到降序单调最短路径）。
我预先计算了从源顶点到所有其他顶点的升序单调最短路径（这可以在 O(E) 中完成，因为它只是一棵最短路径树）。
然后我预先计算了所有顶点对的降序单调最短路径，因为任何顶点都可以是中间顶点，任何顶点都可以是目标顶点。这需要 O(E * V) 时间。
现在，对于从 s 开始到 t 结束的每条路径，我可以检查 (1) 从 s 到中间顶点 v 的上升单调最短路径和 (2) 从 s 开始的下降单调最短路径的所有组合v 到 t 和 select 权重最低的路径。 这会给我一条从 s 到 t 的双调最短路径。
但是，有一个问题：我们不能在路径中有重复的顶点，并且上述想法没有解决这个问题。
对于解决问题的最后一部分有什么想法吗？ 也欢迎解决问题的任何其他ideas/approaches。
（注意：我没有检查你的想法的宏伟计划是否真的成立，或者是否有更快的算法。这仅解决重复顶点的问题。）
假设递减路径和递增路径都不包含重复顶点，重复顶点的唯一机会是如果一个顶点同时存在于"bitonic"路径的递减和递增部分。
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，其中两条连续的边具有相同的权重。但是根据你的定义 "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"，这应该仍然是双调路径，因为 A --1-- C 和 C --1-- Z 分别是严格单调递增和单调递减。
原来答案看起来比我想象的要简单
我评论的策略是 (1) 预计算从源顶点到所有其他顶点的单调升序最短路径，(2) 预计算所有顶点对的降序单调最短路径，以及, (3) 对于从 s 开始到 t 结束的每条路径，检查从 s 到中间顶点 v 的升序单调最短路径和从 v 到 t 的降序单调最短路径的所有组合仅在路径可以具有重复顶点时有效.
当我们寻找简单的路径（没有重复的顶点）时，我们可以 (1) 按升序松弛图中的所有边，然后，在这些相同的路径上，(2) 松弛图中的所有边图降序排列。当我们按升序松弛边时，我们确保丢弃仅下降的路径，或者所有边具有相同权重的路径（除非恰好有 2 个边具有相同的权重，请参阅下面我对这个边缘情况的评论）。当按降序松弛边时，我们丢弃只有上升边权重的路径。
这是我想出的算法的大概思路。还涉及一些实现细节：优先级队列用于两个放宽，路径对象按最小权重排序。重要的是要考虑具有恰好 2 个权重相等的边的路径的边缘情况（根据问题定义，这是一条双调路径）。
运行时复杂度似乎是 O(P lg P)，其中 P 是图中路径的数量。
代码及其依赖和测试可以在我的GitHub中找到，在这个class中：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;
}
}