Блог

Поэтому я попытался написать алгоритм Дейкстры для следующего графика. Я использовал очередь приоритетов, чтобы временная сложность могла быть меньше V^2 ( где » V » — общее количество вершин).

Мой подход ->

 public static class Pair implements Comparator<Pair> {
        int vertex;
        int weight;

        Pair(){}

        Pair(int vertex,int weight){
            this.vertex=vertex;
            this.weight=weight;
        }

        @Override
        public int compare(Pair pairOne, Pair pairTwo) {
            return Integer.compare(pairOne.weight,pairTwo.weight);
        }
    }

public static void shortestPath(ArrayList<ArrayList<Pair>> adjList,int vertices,int source){
        int count=0;
        int[] distance=new int[vertices];
        boolean[] spt=new boolean[vertices];
        for(int i=0;i<vertices;i  ){
            distance[i]=Integer.MAX_VALUE;
        }
        distance[source]=0;
        spt[source]=true;
        PriorityQueue<Pair> ourPriorityQueue=new PriorityQueue<>(vertices,new Pair());
        ourPriorityQueue.add(new Pair(source,distance[source]));

        while(!ourPriorityQueue.isEmpty()){
            Pair poppedElement=ourPriorityQueue.poll();
            spt[poppedElement.vertex]=true;
            count  ;
            for(Pair pair:adjList.get(poppedElement.vertex)){
                if(!spt[pair.vertex] amp;amp; distance[pair.vertex]>distance[poppedElement.vertex] pair.weight){
                    distance[pair.vertex]=distance[poppedElement.vertex] pair.weight;
                    ourPriorityQueue.add(new Pair(pair.vertex,distance[pair.vertex]));
                }
            }
        }
        for(int i=0;i<vertices;i  ){
            System.out.println("Distance of "   i   " from source is "   distance[i]);
        }
        System.out.println(count);
    }
 

Единственное сомнение, с которым я столкнулся, заключалось в том, что мой внешний цикл выполняется более » V » раз, так как одни и те же вершины с разным весом добавляются более одного раза в очередь приоритетов. Так как внешний цикл выполняется более «V» раз. не станет ли временная сложность больше O(VLogV) ? Печать переменной count доказывает, что цикл выполняется более V раз