2

私はJavaのアルゴリズム、パート 5: グラフ アルゴリズム、第 3 版の本のコードに従っており、294 ページでは、プリムの最小スパニング ツリー (MST) アルゴリズムを変更することで、古典的なダイクストラ アルゴリズムを使用できると説明しています (これは私がテストして動作します)。優先度の割り当てを、エッジの重みからソースからエッジの宛先までの距離に変更します。問題は、私が変更を加えると、それに続く条件が決して評価されないことであり、当然のことです。は、eg に初期化された double 配列であるため、 andが何であれ、この条件は成立しません (重みが負でない場合):P = e->wt()P = wt[v] + e->wt()truewtDouble.MAX_VALUEvw

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

本のウェブサイトをチェックしましたが、正誤表はありません。

これは、本からのテストケースで実行可能な Main を備えた私の自己完結型のコードです。

更新:

  • wt[getSource().index] = 0.0;回答の1つからのフィードバックに続いて、初期化行を追加しました。ソース頂点は、距離がゼロの 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(ダイクストラは単一ソースの最短パスです。ソースが必要です!) ! 本について: 彼らがその部分を忘れた場合、彼らの悪い :-P

于 2013-01-19T13:47:35.297 に答える