Почему мой алгоритм Дейкстры работает для отрицательных весов? Я реализовал это неправильно, и я жертвую временем выполнения? - PullRequest
Новая
       55

Почему мой алгоритм Дейкстры работает для отрицательных весов? Я реализовал это неправильно, и я жертвую временем выполнения?

1 голос
/ 20 апреля 2020 
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;
        }
    }
}

Могу ли я получить помощь, чтобы выяснить, что не так с моим кодом? Это работает для положительных и отрицательных взвешенных ребер, если они не находятся в отрицательном цикле. Я пытался изучить это, но я не уверен, где я ошибся. Я предполагаю, что то, что я сделал неправильно, в основном повлияет на сложность времени, но я все еще могу ошибаться.

1 Ответ

2 голосов
/ 20 апреля 2020

Дейкстры всегда должны находить решение, пока оно существует и нет отрицательных циклов. Однако, если есть отрицательные грани стоимости, найденное решение не обязательно будет решением самая низкая стоимость . Например, путь с весами [1, -10] будет возвращен перед путем с весами [1,10, -100].

...