其中数据类型在Dijkstra算法的队列中使用？ [英] Which datatype to use as queue in Dijkstra's algorithm?

问题描述

我想实现Dijkstra算法在Java中（自学）。我用维基百科（链接）提供的伪code。现在，附近的算法结束时，我应该减小键v Q中; 。我想我应该已经实现了Q与BinaryHeap中或类似的东西？什么是正确的（内置），数据类型在这里使用？

 私人无效的Dijkstra（INT源）{
        INT [] DIST =新INT [this.adjacencyMatrix.length]
        INT [] previous =新INT [this.adjacencyMatrix.length]
        队列＆LT;整数GT; Q =新的LinkedList＆LT;整数GT;（）;

        的for（int i = 0; I＆LT; this.adjacencyMatrix.length;我++）{
            DIST [我] = this.INFINITY;
            previous [我] = this.UNDEFINED;
            q.add（ⅰ）;
        }

        DIST [来源] = 0;

        而（！q.isEmpty（））{
            //获取节点最小的地区;
            INT U = 0;
            的for（int i = 0; I＆LT; this.adjacencyMatrix.length;我++）{
                如果（DIST [1]  - ;测距[U]）
                    U = I;
            }

            如果DIST //突破== INFINITY
            如果（DIST [U] == this.INFINITY）破;

            //从q拆除ü
            q.remove（U）;

            的for（int i = 0; I＆LT; this.adjacencyMatrix.length;我++）{
                如果（this.adjacencyMatrix [U] [I] == 1）{
                    //在加权图，this.adjacencyMatrix [U] [I]总是== 1;
                    INT ALT = DIST [U] + this.adjacencyMatrix [U] [我]
                    如果（ALT＆LT;测距[I]）{
                        DIST [我] = ALT;
                        previous [i] = U;

                        //这里就是我应该减少键
                    }
                }
            }
        }
    }
 

解决方案

的优先级队列的根据维基文章。这表明了经典的实施现在是使用由斐波那契堆实现的最小优先级的队列。

I'm trying to implement Dijkstra's algorithm in Java (self-study). I use the pseudo-code provided by Wikipedia (link). Now near the end of the algorithm, I should decrease-key v in Q;. I guess i should have implemented Q with a BinaryHeap or something like that? What would be the right (built-in) datatype to use here?

private void dijkstra(int source) {
        int[] dist = new int[this.adjacencyMatrix.length];
        int[] previous = new int[this.adjacencyMatrix.length];
        Queue<Integer> q = new LinkedList<Integer>();

        for (int i = 0; i < this.adjacencyMatrix.length; i++) {
            dist[i] = this.INFINITY;
            previous[i] = this.UNDEFINED;
            q.add(i);
        }

        dist[source] = 0;

        while(!q.isEmpty()) {
            // get node with smallest dist;
            int u = 0;
            for(int i = 0; i < this.adjacencyMatrix.length; i++) {
                if(dist[i] < dist[u])
                    u = i;
            }

            // break if dist == INFINITY
            if(dist[u] == this.INFINITY) break;

            // remove u from q
            q.remove(u);

            for(int i = 0; i < this.adjacencyMatrix.length; i++) {
                if(this.adjacencyMatrix[u][i] == 1) {
                    // in a unweighted graph, this.adjacencyMatrix[u][i] always == 1;
                    int alt = dist[u] + this.adjacencyMatrix[u][i]; 
                    if(alt < dist[i]) {
                        dist[i] = alt;
                        previous[i] = u;

                        // here's where I should "decrease the key"
                    }
                }
            }
        }
    }

解决方案

Priority Queue as per the wiki article. Which suggests that the classic implementation now is to use a "min-priority queue implemented by a Fibonacci heap."

这篇关于其中数据类型在Dijkstra算法的队列中使用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！