Алгоритм Джикстра, использующий приоритетную очередь, не работает - PullRequest
Новая
       34

Алгоритм Джикстра, использующий приоритетную очередь, не работает

0 голосов
/ 24 апреля 2020 
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //Adjacency list

        ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
        int nodes = sc.nextInt();
        int edges = sc.nextInt();
        for (int i = 0; i < nodes; i++) {
            graph.add(new ArrayList<Edge>());
        }
         //Adding edges
        for (int i = 0; i < edges; i++) {
            int s = sc.nextInt();
            int d = sc.nextInt();
            int l = sc.nextInt();
            Edge e = new Edge(d, l);
            Edge f = new Edge(s, l);
            graph.get(s).add(e);
            graph.get(d).add(f);
        }
        //calling djikstra method

        shortestPath(graph, nodes);
    }
    public static void shortestPath(ArrayList<ArrayList<Edge>> list, int n) {
       //Initalising the priority Queue

        PriorityQueue<Edge> pq = new PriorityQueue<>(n, new Edge());

        //visited array to mark visited nodes

        boolean visited[] = new boolean[n];
        //distance array to store distance
        int distance[] = new int[n];

        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0;
        pq.add(new Edge(0, 0));
        HashSet<Integer> set = new HashSet<>();
        while (!pq.isEmpty()) {
            int u = pq.remove().dest;
            set.add(u);
            calculate(u, list, pq, set, distance);

        }
        for (int i = 0; i < n; i++) {
            System.out.println(i + " " + distance[i]);
        }
    }
    public static void calculate(int u, ArrayList<ArrayList<Edge>> list, PriorityQueue<Edge> pq, HashSet<Integer> set, int distance[]) {
        int edge = -1;
        int newd = -1;
        for (int i = 0; i < list.get(u).size(); i++) {
            Edge v = list.get(u).get(i);
            if (!set.contains(v.dest)) {
                edge = v.len;
                newd = distance[u] + edge;
                if (distance[v.dest] > newd) {
                    distance[v.dest] = newd;

                }
                pq.add(new Edge(v.dest, distance[v.dest]));
            }
        }
    }
}


class Edge implements Comparator<Edge>
 {

    int dest, len;
    public Edge() {}
    public Edge(int d, int l) {

        dest = d;
        len = l;
    }
    public String toString() {
        return dest + " , " + len;
    }
    public int compare(Edge e1, Edge e2) {
        return e1.len - e2.len;
    }

}

Теперь я отправляю это решение в онлайн-судью, на котором я записался на курс, и оно дает неправильный ответ на некоторые тестовые случаи. Я не знаю тестовых случаев, они не предоставляют это. Также решение принимается, если я не использую приоритетную очередь и не выполняю классический метод поиска минимальной вершины.

Будет очень полезно, если вы сможете найти ошибку.

...