java 中的 Dijkstra 算法

Question

我正在我的一个项目中实施 Dijkstra 算法，但是当我通过这些要点时：

Vertex A = new Vertex("A");
Vertex B = new Vertex("B");
Vertex D = new Vertex("D");
Vertex F = new Vertex("F");
Vertex K = new Vertex("K");


// set the edges and weight
A.adjacencies = new Edge[]{ new Edge(B, 6) };
A.adjacencies = new Edge[]{ new Edge(D, 8) };

B.adjacencies = new Edge[]{ new Edge(F, 5) };
D.adjacencies = new Edge[]{ new Edge(F, 3) };
B.adjacencies = new Edge[]{ new Edge(A, 6) };
D.adjacencies = new Edge[]{ new Edge(A, 8) };

F.adjacencies = new Edge[]{ new Edge(B, 5) };
F.adjacencies = new Edge[]{ new Edge(D, 3) };
F.adjacencies = new Edge[]{ new Edge(K, 40) };

K.adjacencies = new Edge[]{ new Edge(F, 40) };

 computePaths(A); // run Dijkstra
System.out.println("Distance to " + K + ": " + K.minDistance);
List<Vertex> path2 = getShortestPathTo(K);
System.out.println("Path: " + path2);

算法给我：到 K 的距离：无限问题出在哪里？

这是算法的完整代码：

   class Vertex implements Comparable<Vertex>
{
    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }
    public int compareTo(Vertex other)
    {
        return Double.compare(minDistance, other.minDistance);
    }

}


class Edge
{
    public final Vertex target;
    public final double weight;
    public Edge(Vertex argTarget, double argWeight)
    { target = argTarget; weight = argWeight; }
}

    public void computePaths(Vertex source) {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
        vertexQueue.add(source);

        while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies) {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    vertexQueue.remove(v);

                    v.minDistance = distanceThroughU;
                    v.previous = u;
                    vertexQueue.add(v);
                }
            }
        }}


    public List<Vertex> getShortestPathTo(Vertex target) {
        List<Vertex> path = new ArrayList<Vertex>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);

        Collections.reverse(path);
        return path;
    }

知道为什么距离 = 无穷大吗？

Answer 1

您在此处覆盖该字段的值。当您分配新值 Edge[] 时，旧值将被删除。
您是否打算改为添加？

B.adjacencies = new Edge[]{ new Edge(F, 5) };
D.adjacencies = new Edge[]{ new Edge(F, 3) };
B.adjacencies = new Edge[]{ new Edge(A, 6) };
D.adjacencies = new Edge[]{ new Edge(A, 8) };

要为每个 Vertex 分配多个 Edges，请使用具有多个元素的数组初始值设定项：

A.adjacencies = new Edge[]{ new Edge(B, 6), new Edge(D, 8) };
B.adjacencies = new Edge[]{ new Edge(F, 5), new Edge(A, 6) };
D.adjacencies = new Edge[]{ new Edge(F, 3), new Edge(A, 8) };
F.adjacencies = new Edge[]{ new Edge(B, 5), new Edge(D, 3), new Edge(K, 40)};

java 中的 Dijkstra 算法

Dijkstra's algorithm in java

java

dijkstra