图邻域定义有向图在Java中实现Dijkstra算法？

Question

我的问题是

>

如何定义顶点的邻接列表？在我下面的当前代码中，我只考虑了邻接列表部分的传出边

如果图中存在带的循环模式，Dijkstra的算术运算是否失败？例如，ABD形成以下循环：

我已经实现了Dijsktra的算法，但我没有在这里粘贴该代码。在澄清了这些疑问之后，我将就Dijkstra的实现问题发布一个单独的问题。

我当前的顶点、边缘和图形代码如下。正如您所注意到的，我已经为上面的图像定义了顶点和邻接列表。如果邻接列表正确，请通过您的评论。例如：顶点F没有邻接列表，因为它没有传出边缘。

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 class Graph { 
public static void main(String[] args) {
        Vertex A = new Vertex("A");
        Vertex B = new Vertex("B");
        Vertex C = new Vertex("C");
        Vertex D = new Vertex("D");
        Vertex E = new Vertex("E");
        Vertex F = new Vertex("F");
        Vertex G = new Vertex("G");

        A.adjacencies = new Edge[]{ new Edge(B, 1)};
        B.adjacencies = new Edge[]{ new Edge(C, 3), new Edge(D, 2)};
        C.adjacencies= new Edge[]{new Edge(D, 1),new Edge(E, 4)};
        D.adjacencies= new Edge[]{new Edge(E, 2),new Edge(A, 2) };
        E.adjacencies= new Edge[]{new Edge(F, 3) };
        //F.adjacencies= null;
        G.adjacencies= new Edge[]{new Edge(D, 1)};

    }
}

Answer 1

>

仅使用传出边有效。

不会。好的算法实现不会有循环问题。在算法中，不可能有圈的问题，因为节点越来越多地被“消除”，并且许多边被消除。

对算法将解决这个问题。在开始之前，您必须确保所有中间信息都设置正确，例如，您需要能够识别是否删除了节点。在算法中，您需要选择要开始的节点，如果该节点没有相邻节点，则其他节点（例如A）的previous属性将设置为null。将更容易实现F。邻接=新边[0]