为什么我的 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;
        }
    }
}

我能得到一些帮助来找出我的代码有什么问题吗？它适用于正负加权边缘，只要它们不处于负 cycle.I 尝试调查它但我不确定我哪里出错了。我猜我做错了什么主要只会影响时间复杂度，但我仍然可能是错的。

Answer 1

Dijkstra 应该总能找到 a 解，只要存在并且没有负循环。但是，如果存在负成本边，它找到的解决方案可能不一定是 最低成本 解决方案。例如，权重为 [1,-10] 的路径将在权重为 [1,10,-100] 的路径之前返回。

为什么我的 Dijkstra 算法适用于负权重？我是否错误地实施了它并且牺牲了运行时间？

Why does my Dijkstra algorithm work for negative weights? Did I implement it incorrectly and am I sacrificing runtime?

java

algorithm

dijkstra

weighted-graph