java 优先队列插入键值对java

priority queue insert key value pair java

提问by jessicaraygun

Background

背景

I am trying to code Dijkstra's algorithm in O(mlogn) time, where m is the number of edges and n is the number of nodes. I am using to find the shortest path between a given starting node and a given ending node. And I'm pretty new at this.

我试图在 O(mlogn) 时间内编写 Dijkstra 算法，其中 m 是边数，n 是节点数。我正在使用找到给定起始节点和给定结束节点之间的最短路径。我对此很陌生。

Here is the algorithm I have come up with:

这是我想出的算法：

Assume the graph is represented by an adjacency matrix and each node has a row index.

假设该图由一个邻接矩阵表示，并且每个节点都有一个行索引。

Initialize starting node distance to zero, and all other nodes to inifinity, in the heap.

Create a list of shortest paths, equal to the number of nodes in the graph, set to 0.

While the index of the node that corresponds to the minimum element in the heap 
has no value in the list of shortest paths and heap has node distances, do:
    Remove the minimum node distance from the heap, and bubble as necessary to fill the removed node.
    Put the minimum node distance into the list of shortest paths at its row index.

    For all nodes that were adjacent to the node with the minimum distance (that was just removed), do:
      Update the distances in the heap for the current node, using the following calculation:
        min((deleted node distance + adjacent edge weight), current node's distance)
    Reorganize the heap to be a minimum heap.

Return value in the list of shortest paths at the location of the end node.

This is O(mlogn) because you only update the distances once per edge.

这是 O(mlogn) 因为你只更新每条边一次的距离。

"It takes linear time to initialize the heap, and then we perform m updates at a cost of O(log n) each for a total time of O(mlog n)." - http://www.cs.cmu.edu/~avrim/451f07/lectures/lect1011.pdf

“初始化堆需要线性时间，然后我们以 O(log n) 的成本执行 m 次更新，每次更新的总时间为 O(mlog n)。” - http://www.cs.cmu.edu/~avrim/451f07/lectures/lect1011.pdf

Problem

问题

In order to update the distances from the starting vertex in the correct location in the heap, insertions to the heap must be key-value pairs - with the key being the node (row index) and the value being the distance.

为了更新与堆中正确位置的起始顶点的距离，对堆的插入必须是键值对——键是节点（行索引），值是距离。

There are lecture slides onlinethat say each entry in a priority queue ADT is a key-value pair (otherwise, how could it prioritize?).

网上有讲课幻灯片说优先队列 ADT 中的每个条目都是一个键值对（否则，它如何确定优先级？）。

Question

问题

The methods for PriorityQueuehave at most one parameter, so how do you insert a key associated with a value?

PriorityQueue的方法最多只有一个参数，那么如何插入与值关联的键呢？

This must be done in a single file with a specific name (i.e. It is my understanding that I can't make a KeyValuePairclass implementing Comparator).

这必须在具有特定名称的单个文件中完成（即我的理解是我不能让一个KeyValuePair类实现Comparator）。

I'd love to hear your thoughts.

我很想听听你的想法。

采纳答案by reprogrammer

To use JDK's implementation of priority queue for your application, you can maintain a Map<Key, Value>in addition to PriorityQueue<Value>. In your case, Keyrepresents a node and Valueis an object that holds the shortest distance to a node. To update the distance to a node, you first look up its corresponding distance object in the map. Then, you remove the distance object from the priority queue. Next, you update the distance object. Finally, you insert the distance object back in the priority queue.

要为您的应用程序使用 JDK 的优先级队列实现，您可以维护一个Map<Key, Value>除了PriorityQueue<Value>. 在您的情况下，Key代表一个节点并且Value是一个与节点保持最短距离的对象。要更新到节点的距离，首先要在地图中查找其对应的距离对象。然后，您从优先级队列中删除距离对象。接下来，更新距离对象。最后，您将距离对象重新插入优先级队列中。

回答by RAJAN_PARMAR

Below is the Dijkstra implementation using priority_queue . Here ignore the InputReader class as it is for fast input . We can maintain priority according to "Value" of pair in key value pair . Then choose the Pair with minimum cost i.e value .

下面是使用 priority_queue 的 Dijkstra 实现。这里忽略 InputReader 类，因为它用于快速输入。我们可以根据 key value pair 中 pair 的 "Value" 来维护优先级。然后选择成本最低的 Pair 即 value 。

import java.io.File;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.List;
import java.util.PriorityQueue;
/** 
 * By: Rajan Parmar
 * At : HackerRank 
 **/
public class Dijkstra { 
     // node ,pair ( neighbor , cost)
    static HashMap < Integer , HashSet <Pair>> node;
    static PrintWriter w;   
    public static void main(String [] s) throws Exception{
        InputReader in;

        boolean online = false;
        String fileName = "input";

        node = new HashMap<Integer, HashSet<Pair>>();


        //ignore online if false it is for online competition
        if (online) {

            //ignore
            in = new InputReader(new FileInputStream(
                    new File(fileName + ".txt")));
            w = new PrintWriter(new FileWriter(fileName + "Output.txt"));
        } else {

            // for fast input output . You can use any input method
            in = new InputReader(System.in);
            w = new PrintWriter(System.out);
        }

        // Actual code starts here
        int t;
        int n, m;
        t = in.nextInt();

        while(t-- > 0){
            n = in.nextInt();
            m = in.nextInt();
            while(m-- > 0){
                int x,y,cost;
                x = in.nextInt();
                y = in.nextInt();
                cost = in.nextInt();

                if(node.get(x)==null){
                    node.put(x, new HashSet());
                    node.get(x).add(new Pair(y,cost));
                }
                else{
                    node.get(x).add(new Pair(y,cost));
                }
                if(node.get(y)==null){
                    node.put(y, new HashSet());
                    node.get(y).add(new Pair(x,cost));
                }
                else{
                    node.get(y).add(new Pair(x,cost));
                }
            }
            int source = in.nextInt();
            Dijkstra(source,n);
            node.clear();
            System.out.println("");
        }
    }

    static void Dijkstra(int start , int n) {

        int dist[] = new int[3001];
        int visited[] = new int[3001];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(visited, 0);
        dist[start] = 0 ;
        PriorityQueue < Pair > pq = new PriorityQueue();

        //this will be prioritized according to VALUES (i.e cost in class Pair)
        pq.add(new Pair(start , 0));
        while(!pq.isEmpty()){
            Pair pr = pq.remove();
            visited[pr.neighbor] = 1;
            for(Pair p:node.get(pr.neighbor)){
                if(dist[p.neighbor] > dist[pr.neighbor] + p.cost){
                    dist[p.neighbor] = dist[pr.neighbor] + p.cost;

                    //add updates cost to vertex through start vertex
                    if(visited[p.neighbor]==0)
                        pq.add(new Pair(p.neighbor ,dist[p.neighbor] ));
                }

            }
        }
        for(int i=1;i<=n;i++){
            if(i==start) continue;
            if(visited[i]==0)
                dist[i]=-1;
            System.out.print(dist[i]+" ");
        }
    }

    static class Pair implements Comparable {

        int neighbor;
        int cost;

        public Pair(int y, int cost) {
            // TODO Auto-generated constructor stub
            neighbor = y;
            this.cost = cost;
        }

        @Override
        public int compareTo(Object o) {
            // TODO Auto-generated method stub
            Pair pr = (Pair)o;

            if(cost > pr.cost)
                return 1;
            else
                return -1;

        }

    }

    //Ignore this class , it is for fast input.
    static class InputReader {

        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public String readString() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}

This will take input in following format .

这将采用以下格式输入。

First line be T (no. of test case).

第一行是 T（测试用例的数量）。

For each test case next line input will be N and M , where N is no of nodes , M is no of edges.

对于每个测试用例，下一行输入将是 N 和 M ，其中 N 是节点数，M 是边数。

Next M line contains 3 integers i.e x,y,W. It represents edge between node x and y with weight W.

接下来的 M 行包含 3 个整数，即 x,y,W。它表示节点 x 和 y 之间权重为 W 的边。

Next line contain single integer i.e. Source node .

下一行包含单个整数，即源节点。

Output :

输出 ：

Print shortest distance to all node from given source node . If node is unreachable print -1.

打印从给定源节点到所有节点的最短距离。如果节点无法访问，则打印 -1。

e.g

例如

Input :

输入 ：

1
6 8
1 2 1
1 5 4
2 5 2
2 3 2
5 6 5
3 6 2
3 4 1
6 4 3
1

Output : (shortest distance of all node from node 1)

输出：（所有节点到节点 1 的最短距离）

1 3 4 3 5

回答by jessicaraygun

I appreciate the answers to my question and at the time I chose the Map answer because given my limited understanding of the language, it seemed easier for me to implement.

我很欣赏我的问题的答案，当时我选择了 Map 答案，因为我对语言的理解有限，这对我来说似乎更容易实现。

It turns out that I overlooked an important detail that made the problem much simpler than I thought it was: if I maintain an array of distances and insert the nodes into the heap (instead of the distances), to use as references to the distance array, I was able to sort the nodes based on their values.

事实证明，我忽略了一个重要的细节，使问题比我想象的要简单得多：如果我维护一个距离数组并将节点插入堆（而不是距离）中，以用作对距离数组的引用，我能够根据节点的值对节点进行排序。

In this implementation, I didn't need to contrive a key-value property after all. After updating the values in the distance array, I had to remove and re-add those specific nodes to the heap in order for the heap to stay current and sorted, as suggested by @reprogrammer.

在这个实现中，我根本不需要设计一个键值属性。更新距离数组中的值后，我必须删除这些特定节点并将其重新添加到堆中，以使堆保持最新状态并按照@reprogrammer 的建议进行排序。

Once I changed what I was putting into the heap, the algorithm was very similar to the one found on Wikipedia.

一旦我更改了放入堆中的内容，该算法与在 Wikipedia 上找到的算法非常相似。

Here is the code I ended up using, in case anyone has the same problem. Note: the magic part is the creation of the PriorityQueue (which is similar to what was suggested by @stevevls):

这是我最终使用的代码，以防万一有人遇到同样的问题。注意：神奇的部分是 PriorityQueue 的创建（类似于@stevevls 的建议）：

import java.util.*;
import java.io.File; //Because files were used to test correctness.
import java.lang.Math;

public class Dijkstra{

//This value represents infinity.
public static final int MAX_VAL = (int) Math.pow(2,30);

/* Assumptions:
    If G[i][j] == 0, there is no edge between vertex i and vertex j
    If G[i][j] > 1, there is an edge between i and j and the value of G[i][j] is its weight.
    No entry of G will be negative.
*/


static int dijkstra(int[][] G, int i, int j){
    //Get the number of vertices in G
    int n = G.length;

    // The 'i' parameter indicates the starting node and the 'j' parameter
    // is the ending node.


    //Create a list of size n of shortest paths, initialize each entry to infinity
    final int[] shortestPaths = new int[n];

    for(int k = 0; k < n; k++){
        shortestPaths[k] = MAX_VAL;
    }

    //Initialize starting node distance to zero.
    shortestPaths[i] = 0;

    //Make a Priority Queue (a heap)
    PriorityQueue<Integer> PQ = new PriorityQueue<Integer>(n,
        new Comparator<Integer>()
            {
                public int compare(Integer p, Integer q)
                {
                    return shortestPaths[p] - shortestPaths[q];
                }
            } );

    //Populate the heap with the nodes of the graph
    for(int k = 0; k < n; k++){
        PQ.offer(k);
    }

    //While the heap has elements.
    while(PQ.size() > 0){

    //  Remove the minimum node distance from the heap.
        int minimum = PQ.poll();

    //  Check if graph is disconnected, if so, return -1.
        if(shortestPaths[minimum] == MAX_VAL)
            {
                return -1;
            }
    //  End node has been reached (i.e. you've found the shortest path), return the distance.
        if( minimum == j){
            return shortestPaths[j];
        }

    //  Take the current node and look through the row to see the vertices adjacent to it (neighbours)
        for(int columnIt = 0; columnIt < n; columnIt ++){


    //    Update the distances in the heap for the current node, using the following calculation:
    //      min((deleted node distance + adjacent edge weight), current node's distance)

            if(G[minimum][columnIt] > 0){

                int sum = shortestPaths[minimum] + G[minimum][columnIt];

                shortestPaths[columnIt]= Math.min(sum, shortestPaths[columnIt]);

                if(shortestPaths[columnIt]==sum)
                {
                    PQ.remove(columnIt);
                    PQ.offer(columnIt);
                }
            }
        }
    }
    return -1;
}

Thank you for your answers and advice.

感谢您的回答和建议。

回答by isxaker

---

---

I am resolving the same issue. I know where you can find the answer on you question. It's a great book with example of code - Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

我正在解决同样的问题。我知道你在哪里可以找到你问题的答案。这是一本带有代码示例的好书 -算法，Robert Sedgewick 和 Kevin Wayne 的第 4 版。

---

---

Site bookand Example of code(including an implementation of Dijkstra'salgorithm using a PriorityQueue) This implementation of Dijkstra'salgorithm doesn't use Java's standard PriorityQueueimplementation. Instead it implements IndexMinPQ, which was discussed earlier in the book with a detailed explanation!

网站的书和代码示例（包括实现Dijkstra的使用算法的PriorityQueue）的这种实现的Dijkstra算法不使用Java标准的PriorityQueue实现。相反，它实现了IndexMinPQ，这在本书前面的详细解释中进行了讨论！