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

Question

我试图在给定的一对顶点之间找到最短的一对边不相交的路径，我正在关注这个algorithm，通常是Suurballe's algorithm 我猜。

算法如下：

运行给定一对顶点的最短路径算法（我用的是Dijkstra算法）
将最短路径的每条边（相当于两条相反方向的弧）替换为一条指向源顶点的弧
使上述每条弧的长度为负值
运行最短路径算法（注：该算法要接受负成本）
擦除找到的两条路径的重叠边，并反转第一条最短路径上剩余弧线的方向，使其上的每条弧线现在都指向汇点顶点。所需的一对路径结果。

在那个维基百科中，第一步是找到源节点和目标节点之间的最短路径，我可以通过使用 Dijkstra Algorithm -

正确地做到这一点，如下面的代码所示

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。

Answer 1

我不会写代码，但我可以向您解释如何解决这个问题，并给出它为什么有效的基本思路。我将使用术语 source 和 sink 来表示您正在搜索之间路径的两个节点。

首先，它为什么有效。正如您在示例中注意到的那样，最短路径对不一定包含其中的单个最短路径。此外，如果您找到最短路径并将其删除，您会发现自己处于一种情况，当 no 存在从源到汇的路径时，最短路径为 edge-disjoint你刚刚找到的路径。所以我们需要找到一种方法来改变我们在构建第二条路径时发现的第一条路径。事实上，这正是我们通过添加负权重实现的。

让我们用你的例子来考虑一下。您运行第一个 dijkstra，它为您找到了路径 ABCDZ。现在我们运行第二个dijkstra，我们要找另一条路，AEBFDZ，同时把ABCDZ修改成ABCGZ。它是这样发生的：在第一个 dijstra 之后，您反转该路径中的所有边缘并取消它们的权重。例如，权重为 1 的边 A->B 变为权重为 -1 的边 B->A。这应该很容易做到——您已经有了恢复路径的逻辑。当您恢复路径时，删除它所包含的边，然后将它们以负权重反向添加回去。

对于您的特定示例，我们只关心权重为 1 的边 C->D。在我们运行第一个 dijkstra 之后，它被反转，成为权重为 D->C 的边-1。现在当我们试图找到第二条最短路径时，它会找到一条路径 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 不处理具有负权重的图。所以这里我们有两种方法：方法（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' 的新图将具有两个属性：它不会有任何负权重，并且原始图中 source 和 sink 之间的最短路径将是新图中 source 和 sink 之间的最短路径（反之亦然）。现在你可以在这个新图中运行 dijkstra（因为它没有负权重），并确保你在其中找到的最短路径对应于原始图中的最短路径。

此时您应该能够为示例图获取路径 A-B-C-D-Z 和 A-E-F-D-C-G-Z。请务必在进入第 3 阶段之前到达此阶段。

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

编辑：这是 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);
    }
}

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

Edge disjoint shortest pair algorithm in Java?

java

algorithm

graph

dijkstra