为什么我的Dijkstra算法适用于负权重？我是否实施不正确，是否牺牲了运行时间？

Question

public static void Dijkstra(Hashtable<String,vertex> ht,String start)
    {
        ht.get(start).setWeight(0);
        Set<String> keys = ht.keySet();
        PriorityQueue<vertex> pq = new PriorityQueue<>();

        for(String key: keys)
                pq.offer(ht.get(key));

        while(pq.isEmpty()==false)
        {
            vertex v =  pq.remove();

            if(v.getAdj()!=null)
            {
                LinkedList<Adjacent> ll = v.getAdj();

                while (ll.isEmpty() == false)
                {
                    Adjacent ad = ll.remove();

                    if (ht.get(ad.getName()).getWeight() > v.getWeight() + ad.getEdgeWeight())
                    {
                        vertex vv = ht.get(ad.getName());
                        pq.remove(ht.get(ad.getName()));
                        vv.setWeight(v.getWeight() + ad.getEdgeWeight());
                        vv.setPre(v.getName());
                        pq.offer(vv);
                    }
                }
            }
        }
    }

public static class vertex implements Comparable
    {
        private String pre;
        private int weight;
        private LinkedList<Adjacent> adj= new LinkedList<>();
        private String name;


        public vertex(String name, String adjName, int edgeWeight)
        {
            this.name=name;
            pre="";
            weight=Integer.MAX_VALUE/2;
            if(adjName!=null)
                adj.add(new Adjacent(adjName,edgeWeight));
        }

        public String getPre()
        {
            return pre;
        }

        public void setPre(String pre)
        {
            this.pre = pre;
        }

        public int getWeight()
        {
            return weight;
        }

        public void setWeight(int weight)
        {
            this.weight = weight;
        }

        public void addAdj(String name, int edgeWeight)
        {
            adj.add(new Adjacent(name,edgeWeight));
        }

        public LinkedList<Adjacent> getAdj()
        {
            if(adj.isEmpty()==false)
                return adj;
            return null;
        }

        public String getName()
        {
            return name;
        }

        public void setName(String name)
        {
            this.name = name;
        }

        @Override
        public int compareTo(Object o)
        {
            vertex v = (vertex)o;
            if(weight>v.getWeight())
                return 1;
            return -1;
        }
    }

public static class Adjacent
    {
        private String name;
        private int edgeWeight;

        public Adjacent(String name, int edgeWeight)
        {
            this.name=name;
            this.edgeWeight=edgeWeight;
        }

        public String getName()
        {
            return name;
        }

        public void setName(String name)
        {
            this.name = name;
        }

        public int getEdgeWeight()
        {
            return edgeWeight;
        }

        public void setEdgeWeight(int edgeWeight)
        {
            this.edgeWeight = edgeWeight;
        }
    }
}

我能否获得一些帮助来弄清我的代码有什么问题？只要它们不在负周期中，它就可以用于正负加权边缘。我尝试研究一下，但不确定哪里出错了。我猜我做错了主要是只会影响时间的复杂性，但我仍然可能是错的。

Answer 1

只要存在并且没有负循环，

Dijkstra的应该总是找到a