Java中的边缘不相交最短对算法？

1 回答

• 2

  我不会编写代码，但我可以向您解释如何解决问题，并提供一个基本的想法，为什么它的工作原理 . 我将使用术语 source 和 sink 作为您正在搜索其间路径的两个节点 .

  首先，它为什么有效 . 正如您在示例中所注意到的那样，最短的路径对不一定包含其中的单个最短路径 . 此外，如果您找到最短路径并将其删除，您可能会发现自己处于某种情况，当存在从源到接收器的路径与您刚刚找到的最短路径边缘不相交时 . 所以我们需要找到一种方法来改变我们在构建第二条路径时找到的第一条路径 . 实际上，这正是我们通过添加负权重而实现的 .

  让我们用你的例子来考虑它 . 你运行了第一个dijkstra，它为你找到了路径 ABCDZ . 现在，当我们运行第二个dijkstra时，我们希望找到另一个路径 AEBFDZ ，同时将 ABCDZ 修改为 ABCGZ . 这是它发生的方式：在第一个dijstra之后，你反转该路径中的所有边缘并否定它们的权重 . 例如，权重为1的边 A->B 变为边 B->A ，权重为-1 . 它应该很容易 - 你已经有了恢复路径的逻辑 . 在恢复路径时，删除它所包含的边，然后将它们反向添加，并使用否定权重 .

  对于你的特定例子，我们只关心重量为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 ，正好是两条路径你正在寻找 .

  现在让我们来看看如何明智地实现这个问题 . 您将需要三个独立的阶段 . 我可以为你编写代码，但我相信你会通过自己攻击来学习更多 .

  阶段1.您将需要实现反转边缘的逻辑 . 正如我所说，这非常简单 . 您只需在第一个dijkstra之后恢复路径（您已经有了这样做的逻辑），并且对于该路径中的每个边缘，您将其从图形中删除，然后将其反向添加并取消 .

  阶段2.您需要一个能够在负权重的图形中找到最短路径的函数 . 非常重要的是要注意dijkstra does not 在具有负权重的图上工作 . 所以这里我们有两种方法：方法（a）是使用bellman-ford算法 . 它比dijkstra慢，但确实如此：在负权重的图中找到最短路径 . 方法（b）鲜为人知，但速度更快，并且利用了我们的方式介绍了那些负面重量 . 它的工作方式如下：

  • 首先，当您运行第一个dijkstra时，不要在到达接收器时停止，继续遍历图形并为节点分配距离 . 在第一个dijskstra的末尾，每个节点将与分配给它的源有一定距离 . 将这些值复制到一个名为 pt 的新数组中 . 我们将这些值称为'potentials' .

  • 删除属于第一个路径的边并添加其反转和反转副本（执行第1阶段）

  • 之后，将图中每条边的权重 w[i, j] 更改为 w'[i, j] = w[i, j] + pt[i] - pt[j] ，其中 pt[i] 是顶点的潜力 i . 有趣的是，具有权重 w' 的新图将具有两个属性：它将不具有任何负权重，并且原始图中源和汇之间的最短路径将是新图中源和汇之间的最短路径（反之亦然） ） . 现在你可以在这个新图形中运行dijkstra（因为它没有负权重），并确保你在其中找到的最短路径对应于原始图形中的最短路径 .

  现在，此时您应该能够为示例图获取路径 A-B-C-D-Z 和 A-E-F-D-C-G-Z . 在进入第3阶段之前一定要进入这个阶段 .

  阶段3：当您完成阶段2时，最后一个阶段将实现路径的正确恢复 . 给定第2阶段的两条路径，您需要找到第二条路径中使用的所有负权重，并重新连接路径之间的边 . 还有一个更简单的替代方案，即每个边缘跟踪它是否属于两条路径中的一条 . 如果将某个边添加到具有上边缘的两个路径之一，则将其标记为属于其中一个路径，并且当您使用负权重添加它时，将其标记为不属于 . 在您的示例中，当您找到第一个路径时，边缘 C-D 将首先被标记为属于其中一个路径，然后当您找到第二个路径并向其添加 D-C 时，将其标记为不属于该路径 . 当您有这样的标记时，您可以通过以任何顺序遍历从源到接收器的标记边缘来恢复两条路径 .

  编辑：这里's java code. Note that besides new methods that I introduced, there'是实际 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);
      }
  }
  

  回复于 2024-04-27T05:55:25+08:00