优先队列插入键值对java

Question

背景

我想在O（mlogn）时间编码Dijkstra算法，其中m是边数，n是节点数。我正在使用查找给定起始节点和给定结束节点之间的最短路径。我在这方面很新颖。

这里是算法我已经想出：

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

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. 

这是O（mlogn），因为你只能每更新一次边缘的距离。

“这需要线性时间 初始化堆，然后我们在澳的成本执行米更新（log n）的每一个用于O（管理记录n）的总时间。” - http://www.cs.cmu.edu/~avrim/451f07/lectures/lect1011.pdf

问题

为了更新从在堆正确的位置开始顶点的距离，插入到堆必须是键 - 值对 - 键为节点（行索引），值是距离。

有演讲稿online是说，在优先级队列ADT的每个条目是一个键值对（否则，它怎么可能优先级？）。

问题

的为PriorityQueue方法最多只能有一个参数，那么你如何插入一个值相关联的密钥？

这必须在具有特定名称的单个文件中完成（即，我的理解是我无法制作KeyValuePair类实现Comparator）。

我很想听听你的看法。

Answer 1

要使用JDK的应用程序优先级队列实现，除了PriorityQueue<Value>之外，还可以维护Map<Key, Value>。在你的情况，Key表示节点和Value是保持到一个节点的最短距离的对象。要更新到节点的距离，首先在地图上查找其对应的距离对象。然后，您从优先级队列中移除距离对象。接下来，您更新距离对象。最后，将距离对象插回到优先级队列中。

Answer 2

我欣赏的回答我的问题，在我选择了地图的答案，因为给我的语言的了解有限的时间，它似乎更容易为我实现。

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

在此实现，我不需要毕竟以图谋键值属性。在更新距离数组中的值之后，我必须删除并重新将这些特定节点添加到堆中，以便堆保持当前和排序，正如@reprogrammer所建议的那样。

一旦我改变了我放入堆的内容，该算法与the one found on Wikipedia非常相似。

这是我最终使用的代码，以防万一任何人有同样的问题。注：神奇的部分是时Queue（这是类似于被@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; 
} 

谢谢您的解答和建议。

Answer 3

---

我正在解决同样的问题。我知道你在哪里可以找到你的问题的答案。 这是一本以罗伯特·塞奇威克和凯文·韦恩为例的代码示例代码 - 算法第4版。

---

Site book和Example of code（包括使用的PriorityQueueDijkstra的算法的实现） 此实现的Dijkstra算法不使用Java的标准的PriorityQueue实施。相反，它实现了IndexMinPQ，这在本书前面有详细的解释。

Answer 4

以下是使用priority_queue的Dijkstra实现。 这里忽略InputReader类，因为它用于快速输入。我们可以根据键值对中的“值”来维护优先级。然后选择具有最小成本即价值的配对。

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); 
     } 
    } 
} 

这将采取以下格式的输入。

第一行是T（测试用例号）。

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

下一行M包含3个整数，即x，y，W。它代表重量为W的节点x和y之间的边。

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

输出：

从给定源节点打印到所有节点的最短距离。如果节点不可达，则打印-1。

e.g

输入：

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 

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

1 3 4 3 5