2

我正在遵循Java中的算法，第 5 部分：图形算法，第 3 版书的代码，并在第 294 页中描述了我们可以通过修改 Prim 的最小生成树 (MST) 算法来获得经典的 Dijkstra 算法（我测试并工作很好）通过以下方式：将优先级分配从P = e->wt()边缘权重更改P = wt[v] + e->wt()为从源到边缘目的地的距离。问题是，当我进行更改时，随后的条件永远不会评估为true，这是可以理解的。wt是一个双数组，初始化为 egDouble.MAX_VALUE因此无论是什么v和w是，这个条件永远不会成立（假设非负权重）：

P = wt[v] + e->wt();
if (P < wt[w]) { // this can never happen ... bug?
   // ...
}

我检查了这本书的网站，没有发现任何勘误表。

这是我的自包含代码版本，带有可运行的 Main 和书中的测试用例：

更新：

  • wt[getSource().index] = 0.0;在来自答案之一的反馈之后添加了初始化行。源顶点属于距离为零的 SPT。

    import java.util.*;

public class AdjacencyList {
    //=============================================================
    // members
    //=============================================================
    private static class Edge {
        int source;
        int target;
        double weight;
    };
    private static class Vertex {
        int index;
        String name;
        List<Edge> edges = new ArrayList<Edge>();
        public Vertex(int index, String name) {
            this.index = index;
            this.name = name;
        }
    };
    private static final int UNDEFINED = -1;
    private int edgesCount = 0;
    private final Vertex[] vertices;
    private final boolean digraph;
    private int orderCount;

    //=============================================================
    // public
    //=============================================================
    public AdjacencyList(int verticesCount, boolean digraph) {
        this.vertices = new Vertex[verticesCount];
        this.digraph = digraph;
    }

    public Vertex createVertex(int index) {
        return createVertex(index, String.valueOf(index));
    }

    public Vertex createVertex(int index, String name) {
        Vertex vertex = new Vertex(index, name);
        vertex.index = index;
        vertex.name = name;
        vertices[index] = vertex;

        return vertex;
    }

    public Edge addEdge(int begin, int end, double weight) {
        return addEdge(vertices[begin], vertices[end], weight);
    }

    public Edge addEdge(Vertex begin, Vertex end, double weight) {
        edgesCount++;
        Edge edge   = new Edge();
        edge.source = begin.index;
        edge.target = end.index;
        edge.weight = weight;
        vertices[begin.index].edges.add(edge);
        if (!digraph) {
            Edge reverse = new Edge();
            reverse.source = end.index;
            reverse.target = begin.index;
            reverse.weight = edge.weight;
            vertices[end.index].edges.add(reverse);
        }
        return edge;
    }

    // inefficient find edge O(V)
    public Edge findEdge(int begin, int end) {
        Edge result = null;
        Vertex vertex = vertices[begin];
        List<Edge> adjacency = vertex.edges;
        for (Edge edge : adjacency) {
            if (edge.target == end) {
                result = edge;
                break;
            }
        }
        return result;
    }

    // inefficient remove edge O(V)
    public void removeEdge(int begin, int end) {
        edgesCount--;
        removeOneEdge(begin, end);
        if (!digraph) {
            removeOneEdge(end, begin);
        }
    }

    public final Vertex[] getVertices() {
        return vertices;
    }

    public int getVerticesCount() {
        return vertices.length;
    }

    public int getEdgesCount() {
        return edgesCount;
    }

    public Vertex getSource() {
        return vertices[0];
    }

    public Vertex getSink() {
        return vertices[vertices.length - 1];
    }

    public void dijkstra() {
        int verticesCount = getVerticesCount();
        double[] wt = new double[verticesCount];
        for (int i = 0; i < wt.length; i++) {
            wt[i] = Double.MAX_VALUE;
        }
        wt[getSource().index] = 0.0;
        Edge[] fr  = new Edge[verticesCount];
        Edge[] mst = new Edge[verticesCount];
        int min = -1;
        Edge edge = null;
        for (int v = 0; min != 0; v = min) {
            min = 0;
            for (int w = 1; w < verticesCount; w++) {
                if (mst[w] == null) {
                    double P = 0.0;
                    edge = findEdge(v, w);
                    if (edge != null) {
                        if ((P = wt[v] + edge.weight) < wt[w]) {
                            wt[w] = P;
                            fr[w] = edge;
                        }
                    }

                    if (wt[w] < wt[min]) {
                        min = w;
                    }
                }
            }

            if (min != 0) {
                mst[min] = fr[min];
            }
        }

        for (int v = 0; v < verticesCount; v++) {
            if (mst[v] != null) {
                System.out.print(mst[v].source + "->" + mst[v].target + " ");
            }
        }
    }

    public void pushRelabel() {
        // TODO
    }

    //=============================================================
    // private
    //=============================================================

    private void removeOneEdge(int begin, int end) {
        Vertex beginVertex = vertices[begin];
        List<Edge> adjacency = beginVertex.edges;
        int position = -1;
        for (int i = 0; i < adjacency.size(); i++) {
            if (adjacency.get(i).target == end) {
                position = i;
                break;
            }
        }
        if (position != -1) {
            adjacency.remove(position);
        }
    }

    private static AdjacencyList createDijkstraGraph() {
        int numberOfVertices = 6;
        boolean directed = true;
        AdjacencyList graph = new AdjacencyList(numberOfVertices, directed);
        for (int i = 0; i < graph.getVerticesCount(); i++) {
            graph.createVertex(i);
        }
        graph.addEdge( 0, 1, .41);
        graph.addEdge( 1, 2, .51);
        graph.addEdge( 2, 3, .50);
        graph.addEdge( 4, 3, .36);
        graph.addEdge( 3, 5, .38);
        graph.addEdge( 3, 0, .45);
        graph.addEdge( 0, 5, .29);
        graph.addEdge( 5, 4, .21);
        graph.addEdge( 1, 4, .32);
        graph.addEdge( 4, 2, .32);
        graph.addEdge( 5, 1, .29);
        return graph;
    }

    /**
     * Test main
     *
     * @param args
     */
    public static void main(String[] args) {
        // build the graph and test dijkstra shortest path
        AdjacencyList directedDijkstra = createDijkstraGraph();
        // expected:
        System.out.println("\n\n*** testing dijkstra shortest path");
        directedDijkstra.dijkstra();
    }
}
4

1 回答 1

1

你弄错了，因为 v != w, wt[v] + e->wt() 可以小于 wt[w]。实际的错误是你需要设置wt[source] = 0（dijkstra是单源最短路径，你需要一个源！）！关于这本书：如果他们忘记了那部分，他们的坏:-P

于 2013-01-19T13:47:35.297 回答