자바 구현, 우선 순위 큐

Question

나는

int evaluationNode = getMinDistances(); 

settled.add(evaluationNode); 

checkNeighbours(evaluationNode); 

오류 쇼 형식이 일치를 할당 한 후 하나의 오류를 알아낼 힘든 시간을 가지고있다. 누구든지이 일을 도와 주시면 감사하겠습니다. 아래는 완벽한 코드입니다.

import java.util.HashSet;

import java.util.InputMismatchException; 

import java.util.PriorityQueue; 

import java.util.Scanner; 

import java.util.Set; 
import java.util.Comparator; 




public class DijkstraPriorityQueue 

{ 

    private int distances[]; 

    private Set<Integer> settled; 


    private PriorityQueue<Node> priorityQueue; 

    private int number_of_nodes; 

    private int adjacencyMatrix[][]; 


    public DijkstraPriorityQueue(int number_of_nodes) 
    { 

     this.number_of_nodes = number_of_nodes; 

     distances = new int[number_of_nodes + 1]; 

     settled = new HashSet<Integer>(); 

     priorityQueue = new PriorityQueue<Node>(number_of_nodes,new Node()); 

     adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1]; 

    } 

    public void dijkstra_algorithm(int adjacency_matrix[][], int source) 
    { 

     int evaluationNode; 

     for (int i = 1; i <= number_of_nodes; i++) 

      for (int j = 1; j <= number_of_nodes; j++) 

       adjacencyMatrix[i][j] = adjacency_matrix[i][j]; 


     for (int i = 1; i <= number_of_nodes; i++) 
     { 
      distances[i] = Integer.MAX_VALUE; 
     } 

     priorityQueue.add(new Node(source, 0)); 

     distances[source] = 0; 

     while (!priorityQueue.isEmpty()) 
     { 

      evaluationNode = getMinDistances(); 

      settled.add(evaluationNode); 

      evaluateNeighbours(evaluationNode); 

     } 

    } 

    private int getMinDistances() 
    { 

     int node = priorityQueue.remove(); 

     return node; 

    } 

    private void checkNeighbours(int evaluationNode) 
    { 

     int edgeDistance = -1; 

     int newDistance = -1; 


     for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++) 
     { 
      if (!settled.contains(destinationNode)) 
      { 
       if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE) 
       { 

        edgeDistance = adjacencyMatrix[evaluationNode][destinationNode]; 

        newDistance = distances[evaluationNode] + edgeDistance; 

        if (newDistance < distances[destinationNode]) 
        { 
         distances[destinationNode] = newDistance; 
        } 

        priorityQueue.add(new Node(destinationNode,distances[destinationNode])); 
       } 
      } 
     } 
    } 

공공 정적 무효 메인 (문자열 []에 args)이 getMinDistances 방법에서

{ 

     int adjacency_matrix[][]; 

     int number_of_vertices; 

     int source = 0; 

     Scanner scan = new Scanner(System.in); 

     try 

     { 

      System.out.println("Enter the number of vertices"); 

      number_of_vertices = scan.nextInt(); 

      adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1]; 



      System.out.println("Enter the Weighted Matrix for the graph"); 

      for (int i = 1; i <= number_of_vertices; i++) 

      { 

       for (int j = 1; j <= number_of_vertices; j++) 

       { 

        adjacency_matrix[i][j] = scan.nextInt(); 

        if (i == j) 

        { 

         adjacency_matrix[i][j] = 0; 

         continue; 

        } 

        if (adjacency_matrix[i][j] == 0) 

        { 

         adjacency_matrix[i][j] = Integer.MAX_VALUE; 

        } 

       } 

      } 



      System.out.println("Enter the source "); 

      source = scan.nextInt(); 



      DijkstraPriorityQueue dijkstrasPriorityQueue = new DijkstraPriorityQueue(number_of_vertices); 

      dijkstrasPriorityQueue.dijkstra_algorithm(adjacency_matrix, source); 



      System.out.println("The Shorted Path to all nodes are "); 

      for (int i = 1; i <= dijkstrasPriorityQueue.distances.length - 1; i++) 

      { 

       System.out.println(source + " to " + i + " is " + dijkstrasPriorityQueue.distances[i]); 

      } 

     } catch (InputMismatchException inputMismatch) 

     { 

      System.out.println("Wrong Input Format"); 

     } 

     scan.close(); 

    } 

} 

class Node implements Comparator<Node> 

{ 

    public int node; 

    public int cost; 



    public Node() 

    { 

    } 



    public Node(int node, int cost) 

    { 

     this.node = node; 

     this.cost = cost; 

    } 



    @Override 

    public int compare(Node node1, Node node2) 

    { 

     if (node1.cost < node2.cost) 

      return -1; 

     if (node1.cost > node2.cost) 

      return 1; 

     return 0; 

    } 

} 

Answer 1

당신은

int node = priorityQueue.remove(); 

를 호출하지만 우선 순위 큐는 Node 객체, 그리고 int 값을 포함 .

은 아마 당신은

private int getMinDistances() 
{ 
    Node node = priorityQueue.remove(); 
    return node.getDistance(); 
} 

같은 것을 원하지만, 이것은 (일명 유래) 디버깅 클라우드 응답 할 수없는 무언가이다.

Answer 2

PriorityQueue를 사용하려면 PriorityQueue를 확장하는 MinPQ를 구현해야하며 MinPQ에서 최소 거리가있는 노드를 반환하는 노드간에 Comparator가 필요합니다.

자세한 내용은 here을 참조하십시오.