java - Dijkstra 算法的优先级队列

Question

我正在研究 Dikjstra 算法的优先级队列。我目前在插入方法上遇到了麻烦。我已经包含了整个类(class)代码，以防您需要更好地了解我要完成的工作。我将堆索引保存在一个数组列表 (heapIndex) 中，将堆保存在另一个数组列表中。

(3 10 6)
(6 50 4)
(8 55 3)
(2 90 5)
(4 60 -1)
(1 75 5)

这是我运行程序后的输出(值、优先级、堆索引)。 *(-1) 表示 heapIndex 中的空单元格。

import java.util.ArrayList;
import java.util.Comparator;


public class DijkstraPriorityQueue<P>{

    private class VertPri{

        public int v;
        public P pri;

        public VertPri(int v2, P priority) {
            v=v2;
            pri=priority;
        }
    }
    private int n;
    private ArrayList<VertPri>heap;
    private ArrayList <Integer>heapIndex;
    private Comparator<P> cmp;

    public DijkstraPriorityQueue(Comparator<P> priorityComparator, int numVerts) {
        cmp=priorityComparator;
        n=0;
        heap=new ArrayList<VertPri>(numVerts+1);
        heapIndex=new ArrayList<Integer>(numVerts+1);
        for(int i =0; i<= numVerts; i++){
            heap.add(null);
            heapIndex.add(-1);
        }
    }

    public boolean isEmpty() {
        return n==0;
    }

    public boolean contains(int v) {
        if(heap.contains(v))
            return true;
        else
            return false;
    }

    public void insert(int v, P priority) {
        n++;
        int hole=n;
        VertPri elem = new VertPri(v , priority);
        VertPri temp;

        for(; hole>1 && heap.get(hole/2) != null && cmp.compare(priority,heap.get(hole/2).pri) < 0; hole/=2){

            heap.set(hole , heap.get(hole/2));
            temp=heap.get(hole/2);
            heapIndex.set(temp.v,hole);
        }
        heap.set(hole,elem);
        heapIndex.set(v, n);

    }

    public int deleteMin() {
        if(n==0)return 0;
        n--;
        VertPri elem=  heap.get(1);
        VertPri temp= heap.get(n--);
        int hole = 1;
        while(2*hole <= n){
            int child = 2*hole;
            if( child != n && cmp.compare(heap.get(child+1).pri,heap.get(child).pri)<0)
                child++;
            if((cmp.compare(heap.get(child).pri,temp.pri) < 0)){
                heap.set(hole, heap.get(child));
                hole=child;
            }else break;
        }
        heap.set(hole,temp);
        heapIndex.set(temp.v, -1);

        return elem.v;
    }

    public void decreaseKey(int v, P priority) {
        VertPri swap;
        int i =heap.indexOf(v);
        if(i==-1){
            return;
        }
        VertPri node= heap.get(i);
        while(i>1 && cmp.compare(priority,heap.get(i/2).pri)<0){
            swap=heap.get(i/2);
            heap.set(i, swap);
            heap.set(swap.v, heap.get(i));
            i=i/2;
        }

        heap.get(v).pri=priority;
        heap.set(i,node);
        heapIndex.set(v,i);
    }

    /*
     * Unit test.
     */
    private static class IntComparator implements Comparator<Integer> {
        public int compare(Integer o1, Integer o2) {
            return o1.compareTo(o2);
        }
    }

    public static void main(String[] args) {
        final int n=10;
        DijkstraPriorityQueue<Integer> Q = 
                new DijkstraPriorityQueue<Integer>(new IntComparator(), n);

        Q.insert(1,75);
        Q.insert(2, 90);
        Q.insert(3, 10);
        Q.insert(4, 60);
        Q.insert(6, 50);
        Q.insert(8, 55);

        for(int i=1; i < 10; i++){
            System.out.println(Q.heap.get(i).v +" "+Q.heap.get(i).pri+" "+ Q.heapIndex.get(i));
        }


            /*  final int n = 20;
        DijkstraPriorityQueue<Integer> Q = 
                new DijkstraPriorityQueue<Integer>(new IntComparator(), n);
        for (int i = 0; i < 20; i++) 
            Q.insert(i, (i-10)*(i-10) + i);
        for (int i = 10; i < 20; i++)
            Q.decreaseKey(i,(i-5)*(i-5));
        while (!Q.isEmpty()) {
            int v = Q.deleteMin();
            System.out.println(v);*/
            //  }
        }
}

Answer 1

这是 ayush nigam的 Dijkstra 算法代码(C++)，来自 Priority queue in Dijkstra's algorithm

    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<queue>

    #define pp pair<int,int>
    using namespace std;
    struct pri
    {
        int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
        {
            return p1.second<p2.second;
        }
    }p;
    int main()
    {
        priority_queue<pp,vector<pp>,pri> q;
        int n;
        cin>>n;
        vector<pp> g[n+1];
        int e,u,v,w,i;
        cin>>e;
        for(i=0;i<e;i++)
        {
            cin>>u>>v>>w;
            g[u].push_back(pp(v,w));
            g[v].push_back(pp(u,w));
        }
        int s;
        cin>>s;
        int d[n+1];
        for(i=1;i<=n;i++)
            d[i]=999;
        d[s]=0;
        q.push(pp(s,d[s]));
        while(!q.empty())
        {
            u=q.top().first;
            q.pop();
            int size=g[u].size();
            for(int i=0;i<size;i++)
            {
                v=g[u][i].first;
                w=g[u][i].second;
                cout<<u<<" "<<" "<<w<<endl;
                if(d[v]>d[u]+w)
                {
                    d[v]=d[u]+w;
                    q.push(pp(v,d[v]));
                }
            }
        }
        for(i=1;i<=n;i++)
            printf("node %d,min weight=%d\n",i,d[i]);
        return 0;
    }