我怎樣才能改變這個代碼從最小堆到最大堆

Question

我有最小堆的Dijkstra的實現，我試圖改變最小堆到最大堆找到最大路徑，但我不能，輸出是錯誤的 所以，請你能幫我改變這個實現到最大堆？ 非常感謝

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算法不會導致一個算法尋找最長路徑。

在Dijkstra算法，用最小堆實現的，它始終是真的，當一個頂點v加入，你得到的最短路徑距離v。這一事實從觀察中暗示，在兩個頂點之間的路徑中增加更多的邊緣不能使路徑縮短。

但是，您在最長路徑問題中沒有類似觀察。即使您從堆中獲取具有最重邊的頂點v到已發現頂點的集合S，但從s到該頂點的距離可能會通過向路徑添加更多邊來延長。

因此，通過使用最大堆實現Dijkstra算法，您違反了發現頂點的所有路徑都是最優的不變量。

因此，Dijksta算法的變化不能用於解決最長路徑問題。其實the longest path problem is NP-hard。因此，在人們普遍認爲的複雜度假設下，P不等於NP，您不能設計一個保證找到最長路徑的多項式時間算法。不幸的是，這個問題是the longest path probably cannot even be reasonably approximated這個意義上最難的NP難題之一。