優先隊列插入鍵值對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