최소 힙에서 최대 힙으로이 코드를 변경하는 방법

Question

최소 힙을 사용하여 Dijkstra에 대한 구현이 있고 최대 힙으로 min 힙을 변경하여 최대 경로를 찾으려고했으나 출력이 잘못되었습니다. 그래서이 구현을 최대 힙으로 변경할 수 있도록 도와 주시겠습니까? 최소 힙 대신 최대 힙을 사용 다 익스트라의 알고리즘을 구현 많은 감사

public class DikjstraAlgorithm { 
public static void main(String[] args) { 

    Graph graph = new Graph(9); 
    for (int i = 0; i < 9; i++) { 
     graph.addVertex(i); 
    } 
    graph.addEdge(0, 1, 4); 
    graph.addEdge(0, 7, 8); 
    graph.addEdge(1, 0, 4); 
    graph.addEdge(1, 7, 11); 
    graph.addEdge(1, 2, 8); 
    graph.addEdge(2, 1, 8); 
    graph.addEdge(2, 3, 7); 
    graph.addEdge(2, 8, 2); 
    graph.addEdge(2, 5, 4); 
    graph.addEdge(3, 2, 7); 
    graph.addEdge(3, 4, 9); 
    graph.addEdge(3, 5, 14); 
    graph.addEdge(4, 3, 9); 
    graph.addEdge(4, 5, 10); 
    graph.addEdge(5, 2, 4); 
    graph.addEdge(5, 3, 14); 
    graph.addEdge(5, 4, 10); 
    graph.addEdge(5, 6, 2); 
    graph.addEdge(6, 5, 2); 
    graph.addEdge(6, 7, 1); 
    graph.addEdge(6, 8, 6); 
    graph.addEdge(7, 0, 8); 
    graph.addEdge(7, 1, 11); 
    graph.addEdge(7, 6, 1); 
    graph.addEdge(7, 8, 7); 
    graph.addEdge(8, 2, 2); 
    graph.addEdge(8, 6, 6); 
    graph.addEdge(8, 7, 7); 
    graph.findShortestPaths(0); 
} 

public static class Graph { 
    Vertex[] vertices; 
    int maxSize; 
    int size; 

    public Graph(int maxSize) { 
     this.maxSize = maxSize; 
     vertices = new Vertex[maxSize]; 
    } 

    public void addVertex(int name) { 
     vertices[size++] = new Vertex(name); 
    } 

    public void addEdge(int sourceName, int destinationName, int weight) { 
     int srcIndex = sourceName; 
     int destiIndex = destinationName; 
     vertices[srcIndex].adj = new Neighbour(destiIndex, weight, vertices[srcIndex].adj); 
     vertices[destiIndex].indegree++; 
    } 

    public void findShortestPaths(int sourceName){ 
     applyDikjstraAlgorith(vertices[sourceName]); 
     for(int i = 0; i < maxSize; i++){ 
      System.out.println("Distance of "+vertices[i].name+" from Source: "+ vertices[i].cost); 
     } 
    } 

    public class Vertex { 
     int cost; 
     int name; 
     Neighbour adj; 
     int indegree; 
     State state; 

     public Vertex(int name) { 
      this.name = name; 
      cost = Integer.MAX_VALUE; 
      state = State.NEW; 
     } 

     public int compareTo(Vertex v) { 
      if (this.cost == v.cost) { 
       return 0; 
      } 
      if (this.cost < v.cost) { 
       return -1; 
      } 
      return 1; 
     } 
    } 

    public enum State { 
     NEW, IN_Q, VISITED 
    } 

    public class Neighbour { 
     int index; 
     Neighbour next; 
     int weight; 

     Neighbour(int index, int weight, Neighbour next) { 
      this.index = index; 
      this.next = next; 
      this.weight = weight; 
     } 
    } 

    public void applyDikjstraAlgorith(Vertex src) { 
     Heap heap = new Heap(maxSize); 
     heap.add(src); 
     src.state = State.IN_Q; 
     src.cost = 0; 
     while (!heap.isEmpty()) { 
      Vertex u = heap.remove(); 
      u.state = State.VISITED; 
      Neighbour temp = u.adj; 
      while (temp != null) { 
       if (vertices[temp.index].state == State.NEW) { 
        heap.add(vertices[temp.index]); 
        vertices[temp.index].state = State.IN_Q; 
       } 
       if (vertices[temp.index].cost > u.cost + temp.weight) { 
        vertices[temp.index].cost = u.cost + temp.weight; 
        heap.heapifyUP(vertices[temp.index]); 
       } 
       temp = temp.next; 
      } 
     } 
    } 

    public static class Heap { 
     private Vertex[] heap; 
     private int maxSize; 
     private int size; 

     public Heap(int maxSize) { 
      this.maxSize = maxSize; 
      heap = new Vertex[maxSize]; 
     } 

     public void add(Vertex u) { 
      heap[size++] = u; 
      heapifyUP(size - 1); 
     } 

     public void heapifyUP(Vertex u) { 
      for (int i = 0; i < maxSize; i++) { 
       if (u == heap[i]) { 
        heapifyUP(i); 
        break; 
       } 
      } 
     } 

     public void heapifyUP(int position) { 
      int currentIndex = position; 
      Vertex currentItem = heap[currentIndex]; 
      int parentIndex = (currentIndex - 1)/2; 
      Vertex parentItem = heap[parentIndex]; 
      while (currentItem.compareTo(parentItem) == -1) { 
       swap(currentIndex, parentIndex); 
       currentIndex = parentIndex; 
       if (currentIndex == 0) { 
        break; 
       } 
       currentItem = heap[currentIndex]; 
       parentIndex = (currentIndex - 1)/2; 
       parentItem = heap[parentIndex]; 
      } 
     } 

     public Vertex remove() { 
      Vertex v = heap[0]; 
      swap(0, size - 1); 
      heap[size - 1] = null; 
      size--; 
      heapifyDown(0); 
      return v; 
     } 

     public void heapifyDown(int postion) { 
      if (size == 1) { 
       return; 
      } 

      int currentIndex = postion; 
      Vertex currentItem = heap[currentIndex]; 
      int leftChildIndex = 2 * currentIndex + 1; 
      int rightChildIndex = 2 * currentIndex + 2; 
      int childIndex; 
      if (heap[leftChildIndex] == null) { 
       return; 
      } 
      if (heap[rightChildIndex] == null) { 
       childIndex = leftChildIndex; 
      } else if (heap[rightChildIndex].compareTo(heap[leftChildIndex]) == -1) { 
       childIndex = rightChildIndex; 
      } else { 
       childIndex = leftChildIndex; 
      } 
      Vertex childItem = heap[childIndex]; 
      while (currentItem.compareTo(childItem) == 1) { 
       swap(currentIndex, childIndex); 
       currentIndex = childIndex; 
       currentItem = heap[currentIndex]; 
       leftChildIndex = 2 * currentIndex + 1; 
       rightChildIndex = 2 * currentIndex + 2; 
       if (heap[leftChildIndex] == null) { 
        return; 
       } 
       if (heap[rightChildIndex] == null) { 
        childIndex = leftChildIndex; 
       } else if (heap[rightChildIndex].compareTo(heap[leftChildIndex]) == -1) { 
        childIndex = rightChildIndex; 
       } else { 
        childIndex = leftChildIndex; 
       } 
      } 
     } 

     public void swap(int index1, int index2) { 
      Vertex temp = heap[index1]; 
      heap[index1] = heap[index2]; 
      heap[index2] = temp; 
     } 

     public boolean isEmpty() { 

      return size == 0; 
     } 
    } 
} 

}

Answer 1

가장 긴 경로를 찾는 알고리즘을 초래하지 않습니다.

최소 힙을 사용하여 구현 된 Dijkstra의 알고리즘에서, 꼭지점 v이 추가되면 v까지의 최단 경로 거리를 얻는 것이 항상 사실입니다. 이 사실은 두 꼭지점 사이의 경로에 더 많은 모서리를 추가해도 경로를 더 짧게 만들 수 없다는 사실로부터 암시됩니다.

그러나 가장 긴 경로 문제에서 비슷한 관찰은 없습니다. 힙에서 가장 큰 에지를 갖는 정점 v을 발견 된 정점의 집합 S에 페치하더라도 s에서 해당 정점까지의 거리가 경로에 더 많은 에지를 추가하여 길어질 수 있습니다.

따라서 최대 힙을 사용하여 다이 st 스트라의 알고리즘을 구현하면 발견 된 버텍스에 대한 모든 경로가 최적이라는 불변성을 위반하게됩니다.

따라서 Dijksta 알고리즘의 변형을 사용하여 가장 긴 경로 문제를 해결할 수 없습니다. 사실, the longest path problem is NP-hard. 따라서 P이 NP과 같지 않다고 널리 알려진 복잡성 가정하에는 가장 긴 경로를 찾을 수있는 다항식 시간 알고리즘을 고안 할 수 없습니다. 불행히도이 문제는 그 의미에서 가장 어려운 NP 어려운 문제 중 하나입니다. the longest path probably cannot even be reasonably approximated.