Java中的边不相交最短对算法？
我试图在给定的顶点对之间找到边不相交的最短路径对，我遵循的是这个算法，我猜它通常是suurballe的算法。
下面是算法：
- 对给定的顶点对运行最短路径算法（我使用的是Dijkstra算法）
- 将最短路径的每条边（相当于两条方向相反的弧）替换为一条朝向源顶点的弧
- 使上述每个弧的长度为负值
- 运行最短路径算法（注意：该算法应接受负成本）
- 擦除找到的两条路径的重叠边，并反转第一条最短路径上剩余弧的方向，使其上的每个弧现在都指向汇顶点。生成所需的路径对。
在wikipedia中，第一步是找到源节点和目的节点之间的最短路径，通过使用Dijkstra算法，我可以正确地做到这一点，如下面的代码所示-
public class DijkstraAlgorithm {
private static final Graph.Edge[] GRAPH = {
new Graph.Edge("A", "G", 8),
new Graph.Edge("A", "B", 1),
new Graph.Edge("A", "E", 1),
new Graph.Edge("B", "C", 1),
new Graph.Edge("B", "E", 1),
new Graph.Edge("B", "F", 2),
new Graph.Edge("C", "G", 1),
new Graph.Edge("C", "D", 1),
new Graph.Edge("D", "F", 1),
new Graph.Edge("D", "Z", 1),
new Graph.Edge("E", "F", 4),
new Graph.Edge("F", "Z", 4),
new Graph.Edge("G", "Z", 2),
};
private static final String START = "A";
private static final String END = "Z";
public static void main(String[] args) {
Graph g = new Graph(GRAPH);
g.dijkstra(START);
// print the shortest path using Dijkstra algorithm
g.printPath(END);
// g.printAllPaths();
}
}
class Graph {
private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges
/** One edge of the graph (only used by Graph constructor) */
public static class Edge {
public final String v1, v2;
public final int dist;
public Edge(String v1, String v2, int dist) {
this.v1 = v1;
this.v2 = v2;
this.dist = dist;
}
}
/** One vertex of the graph, complete with mappings to neighbouring vertices */
public static class Vertex implements Comparable<Vertex> {
public final String name;
public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
public Vertex previous = null;
public final Map<Vertex, Integer> neighbours = new HashMap<Vertex, Integer>();
public Vertex(String name) {
this.name = name;
}
private void printPath() {
if (this == this.previous) {
System.out.printf("%s", this.name);
} else if (this.previous == null) {
System.out.printf("%s(unreached)", this.name);
} else {
this.previous.printPath();
System.out.printf(" -> %s(%d)", this.name, this.dist);
}
}
public int compareTo(Vertex other) {
if (dist==other.dist)
return name.compareTo(other.name);
return Integer.compare(dist, other.dist);
}
}
/** Builds a graph from a set of edges */
public Graph(Edge[] edges) {
graph = new HashMap<String, Vertex>(edges.length);
//one pass to find all vertices
for (Edge e : edges) {
if (!graph.containsKey(e.v1))
graph.put(e.v1, new Vertex(e.v1));
if (!graph.containsKey(e.v2))
graph.put(e.v2, new Vertex(e.v2));
}
//another pass to set neighbouring vertices
for (Edge e : edges) {
graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also for an undirected graph
}
}
/** Runs dijkstra using a specified source vertex */
public void dijkstra(String startName) {
if (!graph.containsKey(startName)) {
System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
return;
}
final Vertex source = graph.get(startName);
NavigableSet<Vertex> q = new TreeSet<Vertex>();
// set-up vertices
for (Vertex v : graph.values()) {
v.previous = v == source ? source : null;
v.dist = v == source ? 0 : Integer.MAX_VALUE;
q.add(v);
}
dijkstra(q);
}
/** Implementation of dijkstra's algorithm using a binary heap. */
private void dijkstra(final NavigableSet<Vertex> q) {
Vertex u, v;
while (!q.isEmpty()) {
u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
if (u.dist == Integer.MAX_VALUE)
break; // we can ignore u (and any other remaining vertices) since they are unreachable
//look at distances to each neighbour
for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
v = a.getKey(); //the neighbour in this iteration
final int alternateDist = u.dist + a.getValue();
if (alternateDist < v.dist) { // shorter path to neighbour found
q.remove(v);
v.dist = alternateDist;
v.previous = u;
q.add(v);
}
}
}
}
/** Prints a path from the source to the specified vertex */
public void printPath(String endName) {
if (!graph.containsKey(endName)) {
System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
return;
}
graph.get(endName).printPath();
System.out.println();
}
/** Prints the path from the source to every vertex (output order is not guaranteed) */
public void printAllPaths() {
for (Vertex v : graph.values()) {
v.printPath();
System.out.println();
}
}
}
现在，我只能执行算法中剩下的步骤，这样我就可以在给定的顶点对之间得到最短的边不相交路径对。
从节点A到节点Z的最短路径是ABCDZ，而最短路径对是ABCGZ和AEBFDZ。
共有1个答案
我不会写代码，但我可以向您解释如何处理这个问题，也给出一个基本的想法为什么它工作。我将使用术语source和sink来表示您正在搜索路径之间的两个节点。
首先，它为什么起作用。正如您在示例中注意到的，最短路径对不一定包含其中的单个最短路径。此外，如果你找到了最短的路径并将其移除，你会发现自己处于这样一种情况，即从源到宿的路径都不存在与你刚刚找到的最短路径边缘不相交的路径。所以我们需要找到一种方法，在建立第二条路径时，能够改变我们找到的第一条路径。事实上，这正是我们通过添加负权重所达到的目的。
让我们用你的例子来考虑一下。运行第一个dijkstra，它为您找到路径abcdz。现在当我们运行第二个dijkstra时，我们想要找到另一个路径AEBFDZ，同时将ABCDZ修改为ABCGZ。它是这样发生的：在第一个dijstra之后，您将该路径中的所有边反转，并求出它们的权重。例如，权重为1的边A->B变为权重为-1的边B->A。这应该很容易--您已经有了恢复路径的逻辑。当您恢复路径时，移除它所组成的边，并将它们反向添加到负权重中。
对于您的特定示例，我们只关心权重为1的边C->d。在我们运行了第一个dijkstra之后，它被反了过来，变成了一个带权重-1的边D->c。现在当我们试图寻找第二条最短路径时，它将找到路径aefdcgz。注意，它包含边d->c，也就是我们刚刚添加的边。在第二条路径中使用这样一个负权重的边意味着什么？好吧，试着把它画在这张纸上，你会看到第一条路径像a-b-c----d-z，第二条像a-e-f-d----c-g-z。如果绘制它，您将注意到可以从两条路径中删除该边(C-D)，并交换它们的尾部。这样做时，路径权重的和不会改变（因为第一条路径的边权重为正，第二条路径的边权重为负），从而产生两条路径a-b-c-g-z和a-e-f-d-z，这两条路径正是您要查找的路径。
现在让我们看看如何明智地实现这个问题。您将需要三个独立的阶段。我本可以为您编写代码，但我确信您可以通过自己攻击它来学到更多。
第一阶段。您将需要实现反转边沿的逻辑。正如我所说的，这是非常直截了当的。您只需在第一个dijkstra之后恢复路径（您已经有了这样做的逻辑），并且对于该路径中的每条边，您将其从图中删除，然后将其反向和反向添加回来。
第二阶段。你需要一个函数，可以在负权重的图中找到最短路径。非常重要的一点是要注意dijkstra对负权的图不起作用。所以这里我们有两种方法：方法(a)是使用bellman-ford算法。它的速度比dijkstra慢，但它确实做到了这一点：在负权值的图中找到一条最短的路径。方法(b)不太为人所知，但速度更快，并且利用了我们引入负权重的方法。其工作方式如下：
>
首先，在运行第一个dijkstra时，到达接收器时不要停止，继续遍历图并为节点分配距离。在第一个dijskstra的末尾，每个节点将有一个与源的距离分配给它。将这些值复制到名为pt的新数组中。我们称这些值为“势”。
删除属于第一条路径的边，并添加它们的反向副本和反向副本（执行阶段1）
现在，您应该能够为示例图获取路径a-b-c-d-z和a-e-f-d-c-g-z。在进入阶段3之前，请务必进入此阶段。
阶段3：当您完成阶段2时，最后一个阶段将是实现路径的正确恢复。给定阶段2的两条路径，您将需要找到第二条路径中使用的所有负权重，并重新连接路径之间的边。还有一个更简单的选择，即每个边沿跟踪它是否属于两条路径中的一条。如果您将某个边添加到具有正边的两条路径中的一条路径上，您将其标记为属于其中一条路径，并且随着您将其添加到负权重，您将其标记为不属于。在您的示例中，当您找到第一条路径时，边C-D将首先标记为属于其中一条路径，然后当您找到第二条路径并将D-C添加到其中时，边C-D标记为不属于其中一条路径。当您有这样的标记时，您可以通过以任何顺序遍历标记的边缘从源到宿来恢复两条路径。
编辑：这里是java代码。注意，除了我介绍的新方法之外，实际的dijkstra方法也有变化。也就是说，它现在在计算alternativedist时使用势。我恢复路径的方法似乎有点复杂，可能有一个更简单的方法。我当前存储了属于答案的所有边的树集。如果我试图添加一个边，而它的反向已经在答案中，那么我将它从答案中移除（它是一个被否定的边的遍历）。然后我就根据那个树集恢复答案。
import java.util.*;
public class DijkstraAlgorithm {
private static final Graph.Edge[] GRAPH = {
new Graph.Edge("A", "G", 8),
new Graph.Edge("A", "B", 1),
new Graph.Edge("A", "E", 1),
new Graph.Edge("B", "C", 1),
new Graph.Edge("B", "E", 1),
new Graph.Edge("B", "F", 2),
new Graph.Edge("C", "G", 1),
new Graph.Edge("C", "D", 1),
new Graph.Edge("D", "F", 1),
new Graph.Edge("D", "Z", 1),
new Graph.Edge("E", "F", 4),
new Graph.Edge("F", "Z", 4),
new Graph.Edge("G", "Z", 2),
};
private static final String START = "A";
private static final String END = "Z";
public static void main(String[] args) {
Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.restorePath(END);
g.revertEdges(END);
g.assignPotentials();
g.dijkstra(START);
g.restorePath(END);
g.printPaths(START, END);
}
}
class Graph {
private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges
/** One edge of the graph (only used by Graph constructor) */
public static class Edge implements Comparable<Edge> {
public final String v1, v2;
public final int dist;
public Edge(String v1, String v2, int dist) {
this.v1 = v1;
this.v2 = v2;
this.dist = dist;
}
public int compareTo(Edge other) {
if (v1.equals(other.v1))
return v2.compareTo(other.v2);
return v1.compareTo(other.v1);
}
}
private TreeSet<Edge> answer = new TreeSet<Edge>(); // stores all the edges in the answer
/** One vertex of the graph, complete with mappings to neighbouring vertices */
public static class Vertex implements Comparable<Vertex> {
public final String name;
public int potential = 0; // is assigned to dist before the second dijkstra
public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
public Vertex previous = null;
public final Map<Vertex, Integer> neighbours = new HashMap<Vertex, Integer>();
public Vertex(String name) {
this.name = name;
}
public int compareTo(Vertex other) {
if (dist==other.dist)
return name.compareTo(other.name);
return Integer.compare(dist, other.dist);
}
}
/** Builds a graph from a set of edges */
public Graph(Edge[] edges) {
graph = new HashMap<String, Vertex>(edges.length);
//one pass to find all vertices
for (Edge e : edges) {
if (!graph.containsKey(e.v1))
graph.put(e.v1, new Vertex(e.v1));
if (!graph.containsKey(e.v2))
graph.put(e.v2, new Vertex(e.v2));
}
//another pass to set neighbouring vertices
for (Edge e : edges) {
graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also for an undirected graph
}
}
/** Runs dijkstra using a specified source vertex */
public void dijkstra(String startName) {
if (!graph.containsKey(startName)) {
System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
return;
}
final Vertex source = graph.get(startName);
NavigableSet<Vertex> q = new TreeSet<Vertex>();
// set-up vertices
for (Vertex v : graph.values()) {
v.previous = v == source ? source : null;
v.dist = v == source ? 0 : Integer.MAX_VALUE;
q.add(v);
}
dijkstra(q);
}
/** Implementation of dijkstra's algorithm using a binary heap. */
private void dijkstra(final NavigableSet<Vertex> q) {
Vertex u, v;
while (!q.isEmpty()) {
u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
if (u.dist == Integer.MAX_VALUE)
break; // we can ignore u (and any other remaining vertices) since they are unreachable
//look at distances to each neighbour
for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
v = a.getKey(); //the neighbour in this iteration
final int alternateDist = u.dist + a.getValue() + u.potential - v.potential;
if (alternateDist < v.dist) { // shorter path to neighbour found
q.remove(v);
v.dist = alternateDist;
v.previous = u;
q.add(v);
}
}
}
}
/** Prints a path from the source to the specified vertex */
public void revertEdges(String endName) {
Vertex v = graph.get(endName);
while (v.previous != null && v.previous != v) {
Vertex w = v.previous;
int weight = v.neighbours.get(w);
v.neighbours.remove(w);
w.neighbours.remove(v);
v.neighbours.put(w, - weight);
v = w;
}
}
public void assignPotentials() {
for (Vertex v : graph.values()) {
v.potential = v.dist;
}
}
/** Stores the path found by dijkstra into the answer */
public void restorePath(String endName) {
Vertex v = graph.get(endName);
while (v.previous != null && v.previous != v) {
String from = v.previous.name;
String to = v.name;
if (answer.contains(new Edge(to, from, 0))) {
answer.remove(new Edge(to, from, 0));
}
else {
answer.add(new Edge(from, to, 0));
}
v = v.previous;
}
}
/** Restores and prints one path based on `answer` dictionary, and removes the edges restored from the answer */
public void printOnePath(String startName, String endName) {
Vertex from = graph.get(startName);
Vertex to = graph.get(endName);
Vertex cur = from;
do {
System.out.printf("%s -> ", cur.name);
Edge e = answer.ceiling(new Edge(cur.name, "", 0));
answer.remove(e);
cur = graph.get(e.v2);
} while (cur != to);
System.out.println(to.name);
}
/** Restores and prints paths based on `answer` dicrionary */
public void printPaths(String startName, String endName) {
printOnePath(startName, endName);
printOnePath(startName, endName);
}
}
-
我有一组原点-终点坐标，我想计算它们之间的最短路径。 我的出发地坐标有时位于一条长直线道路的中间。然而，由OSMNX/NETWorkX计算的最短路径将不考虑中间边缘到最近的节点路径。 OSMnx或networkx中是否有任何现成的函数，我可以使用它来找到在道路中间起点/终点的最短路径？ 如果没有这样的功能，我会考虑使用以下步骤。 获取起点和终点的最近边 获取这些最近边的节点：假设（a，b）为起点，
-
本文向大家介绍Javascript中的最短路径算法，包括了Javascript中的最短路径算法的使用技巧和注意事项，需要的朋友参考一下 在图论中，最短路径问题是在图中的两个顶点（或节点）之间找到路径的问题，以使其构成边的权重之和最小。在这里，我们需要修改添加边缘并添加有向方法，以允许向边缘添加权重。 让我们看看如何添加它- 示例 现在，当在图上添加一条边时，如果我们不指定权重，则会为该边分配默认
-
本文向大家介绍java实现Dijkstra最短路径算法，包括了java实现Dijkstra最短路径算法的使用技巧和注意事项，需要的朋友参考一下 任务描述：在一个无向图中，获取起始节点到所有其他节点的最短路径描述 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra一般的表述
-
主要内容：最短路径算法在给定的图存储结构中，从某一顶点到另一个顶点所经过的多条边称为 路径。 图 1 图存储结构 例如在图 1 所示的图结构中，从顶点 A 到 B 的路径有多条，包括 A-B、A-C-B 和 A-D-B。当我们给图中的每条边赋予相应的权值后，就可以从众多路径中找出总权值最小的一条，这条路径就称为 最短路径。 图 2 无向带权图 以图 2 为例，从顶点 A 到 B 的路径有 3 条，它们各自的总权值是：
-
给定一个无权无向图的邻接矩阵，是否有一种有效的方法（多项式算法）来扩展或增加任意给定的两个结点s和T之间的最短路径长度？ 示例： 在下面的例子中，从顶点S=1到顶点T=5有5条不同的“最短路径”，每个路径的长度为3。我想去除最少的边数，这样最短的路径长度被迫变成4或更多。（断开图形连接是可以的。） 表示此图形： 强制最短路径长度从3增加到4的最小代价是去除两条边（1,2）和（5,9） 目标：
-
本文向大家介绍java实现最短路径算法之Dijkstra算法，包括了java实现最短路径算法之Dijkstra算法的使用技巧和注意事项，需要的朋友参考一下 前言 Dijkstra算法是最短路径算法中为人熟知的一种，是单起点全路径算法。该算法被称为是“贪心算法”的成功典范。本文接下来将尝试以最通俗的语言来介绍这个伟大的算法，并赋予java实现代码。 一、知识准备： 1、表示图的数据结构 用于存储图的