0

我有最小堆的 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;
        }
    }
}

}

4

1 回答 1

1

使用最大堆而不是最小堆实现 Dijkstra 算法不会导致算法找到最长路径。

在使用最小堆实现的 Dijkstra 算法中，当v添加一个顶点时，总是会得到到 的最短路径距离v。从以下观察中可以看出这一事实，即在两个顶点之间的路径中添加更多边不会使路径更短。

但是，您在最长路径问题中没有类似的观察结果。即使您从堆中获取v具有最重边的顶点到已发现的顶点集，也可能通过向路径添加更多边来延长到该顶点S的距离。s

因此，通过使用最大堆实现 Dijkstra 算法，您违反了所有到已发现顶点的路径都是最优的不变量。

因此，Dijksta 算法的变体不能用于解决最长路径问题。事实上，最长路径问题是 NP-hard。因此，在普遍认为P不等于的复杂性假设下NP，您无法设计出保证找到最长路径的多项式时间算法。不幸的是，这个问题是最难的 NP-hard 问题之一，因为最长的路径可能甚至无法合理近似。

于 2017-05-06T17:11:45.303 回答