Dijkstra的最短路徑，HackerRank

Question

我解決問題 - Dijkstra的最短河段2.這裏有一個link。給定包含N個節點（標記爲1到N）的圖，其中特定給定節點S表示起始位置S並且兩個節點之間的邊緣具有給定長度，其可以或可以不等於其他長度圖表。

它需要計算所有圖中的其他節點的從起始位置（節點S）的最短距離。

注：如果一個節點不可達時，距離被假設爲 - 1

輸入格式

第一行包含，表示的測試用例的數量。 每個測試用例的第一行有兩個整數，表示圖中節點的數量，表示圖中邊數。

下一行，每行包括三個空格分開的整數，其中，和表示在其之間無向邊緣存在兩個節點，表示這些相應的節點之間的邊緣的長度。

最後一行具有整數，表示的開始位置。

約束

如果有相同的一對具有不同的權重的節點之間的邊，它們將被作爲被認爲是一樣的多個邊緣。

輸出格式

對於每個測試的情況下，打印由空格隔開的整數，表示比從在增加它們的標籤的順序開始位置的其他節點的最短距離的單行。

無法訪問的節點，打印。

採樣輸入

1 
4 4 
1 2 24 
1 4 20 
3 1 3 
4 3 12 
1 

樣本輸出

24 3 15 

這裏是我的代碼：

Node類

class Node implements Comparator<Node>{ 
    int cost, node; 
    Node(){} 
    Node(int node, int cost){ 
     this.node=node; 
     this.cost=cost; 
    } 
@Override 
public int compare(Node n1, Node n2){ 
    if(n1.cost<n2.cost)return -1; 
    else if(n1.cost>n2.cost)return 1; 
    return 0; 
    } 
} 
class Solution { 
// Working program using Reader Class 
static int adjmatrix[][]; 
static PriorityQueue<Node> pq; 
static boolean visited[]; 
static int distance[]; 
@SuppressWarnings("unchecked") 
static ArrayList<Map<Integer,Integer>> list; 


    static class Reader 
    { 
     final private int BUFFER_SIZE = 1 << 16; 
     private DataInputStream din; 
     private byte[] buffer; 
     private int bufferPointer, bytesRead; 

     public Reader() 
     { 
      din = new DataInputStream(System.in); 
      buffer = new byte[BUFFER_SIZE]; 
      bufferPointer = bytesRead = 0; 
     } 

     public Reader(String file_name) throws IOException 
     { 
      din = new DataInputStream(new FileInputStream(file_name)); 
      buffer = new byte[BUFFER_SIZE]; 
      bufferPointer = bytesRead = 0; 
     } 

     public String readLine() throws IOException 
     { 
      byte[] buf = new byte[64]; // line length 
      int cnt = 0, c; 
      while ((c = read()) != -1) 
      { 
       if (c == '\n') 
        break; 
       buf[cnt++] = (byte) c; 
      } 
      return new String(buf, 0, cnt); 
     } 

     public int nextInt() throws IOException 
     { 
      int ret = 0; 
      byte c = read(); 
      while (c <= ' ') 
       c = read(); 
      boolean neg = (c == '-'); 
      if (neg) 
       c = read(); 
      do 
      { 
       ret = ret * 10 + c - '0'; 
      } while ((c = read()) >= '0' && c <= '9'); 

      if (neg) 
       return -ret; 
      return ret; 
     } 

     public long nextLong() throws IOException 
     { 
      long ret = 0; 
      byte c = read(); 
      while (c <= ' ') 
       c = read(); 
      boolean neg = (c == '-'); 
      if (neg) 
       c = read(); 
      do { 
       ret = ret * 10 + c - '0'; 
      } 
      while ((c = read()) >= '0' && c <= '9'); 
      if (neg) 
       return -ret; 
      return ret; 
     } 

     public double nextDouble() throws IOException 
     { 
      double ret = 0, div = 1; 
      byte c = read(); 
      while (c <= ' ') 
       c = read(); 
      boolean neg = (c == '-'); 
      if (neg) 
       c = read(); 

      do { 
       ret = ret * 10 + c - '0'; 
      } 
      while ((c = read()) >= '0' && c <= '9'); 

      if (c == '.') 
      { 
       while ((c = read()) >= '0' && c <= '9') 
       { 
        ret += (c - '0')/(div *= 10); 
       } 
      } 

      if (neg) 
       return -ret; 
      return ret; 
     } 

     private void fillBuffer() throws IOException 
     { 
      bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
      if (bytesRead == -1) 
       buffer[0] = -1; 
     } 

     private byte read() throws IOException 
     { 
      if (bufferPointer == bytesRead) 
       fillBuffer(); 
      return buffer[bufferPointer++]; 
     } 

     public void close() throws IOException 
     { 
      if (din == null) 
       return; 
      din.close(); 
     } 
    } 
    //////////////////////////////////////////////// 
    public static void initialize(int n){ 
     // adjmatrix=new int[n+1][n+1]; 
     visited=new boolean[n+1]; 
     distance=new int[n+1]; 
     list=new ArrayList<>(n+1); 
     pq=new PriorityQueue<>(new Node()); 
     for(int i=0; i<n+1; ++i)distance[i]=Integer.MAX_VALUE; 
    } 

////////////////////////////////////////////// 
public static void shortestPath(int s){ 
    // int length=adjmatrix.length; 
    int min_node; 
    visited[s]=true; 
    distance[s]=0; 
    pq.add(new Node(s,0)); 
    while(!pq.isEmpty()){ 
     min_node=pq.remove().node; 
     visited[min_node]=true; 
     updateDistance(min_node); 
    } 
} 
/////////////////////////////////////////////// 
//Using adjlist 
private static void updateDistance(int s){ 
    Map<Integer,Integer> current=list.get(s); 
    // Iterator itr=current.entrySet().iterator(); 
    for(Map.Entry<Integer, Integer> entry:current.entrySet()){ 
     int node=entry.getKey(); 
     int cost=entry.getValue(); 
     if(!visited[node]){ 

       distance[node]=Math.min(cost+distance[s], distance[node]); 
       pq.add(new Node(node,distance[node])); 

     } 
    } 

} 

//////////////////////////////////////////////////////////////// 
    public static void main(String []args)throws IOException{ 
     Reader r=new Reader(); 
    //StringBuilder sb = new StringBuilder(); 


    int T=r.nextInt(), N, M; 
    for(int caseNo=1; caseNo<=T; ++caseNo){ 
     N=r.nextInt(); 
     //initialization 
     initialize(N); 
     //initialization of adjacecny matrix 



     M=r.nextInt(); 
     //list=new ArrayList<>(N+1); 
     for(int i=1; i<=N+1; ++i)list.add(new HashMap<Integer, Integer>()); 

     for(int j=1; j<=M; ++j){ 

       int node1=r.nextInt(); 
       int node2=r.nextInt(); 
       int distance=r.nextInt(); 

       if(list.get(node1).get(node2)!=null){ 
        int temp=list.get(node1).get(node2); 
        if(temp<distance)continue; 
       } 

       list.get(node1).put(node2,distance); 
       list.get(node2).put(node1, distance); 

     } 

     //end of graph initialization as a hybrid of adjmatrix and adjlist 

     int s=r.nextInt(); 
     shortestPath(s); 

     for(int i=1; i<=N; ++i)if(i!=s)System.out.print(((distance[i]==Integer.MAX_VALUE)?-1:distance[i])+" "); 
     System.out.println(); 
    }//end of test cases loop[ 
} 
} 

我爲長碼和問題表示歉意。我的程序僅適用於示例測試用例。在其餘部分，它開始正確，但在輸入結束時，它會給出不同的答案。如果需要，我可以粘貼預期輸入和輸出的副本。據我所知，這可能與我如何處理多個無向邊緣的情況有關。我只保持較小的優勢。

P.S.，它現在給正確的值，但速度不夠快。任何優化建議，歡迎您

Answer 1

乍一看你的代碼似乎是正確的（雖然我不是Java的專家）。

下面是我的代碼作爲參考（可能會給你一個想法），&這裏是我的GitHub上的鏈接代碼 Dijkstra hackerrank

實際上它得到了與Queue版本接受（你不必。用minHeap實現它 - 雖然minHeap版本更正確 - Ø（E日誌V）代替鄰（V^2）

這裏是隊列版本： Dijkstra queue version

#include <iostream> 
#include <vector> 
#include <utility> 
#include <limits> 
#include <memory> 
#include <map> 
#include <set> 
#include <queue> 
#include <stdio.h> 


using namespace std; 
using vi = vector<int>; 
using ii = pair<int, int>; 
using vii = vector<ii>; 
const int max_int = 1 << 20; //numeric_limits<int>::max(); 


class Graph{ 
public: 
    Graph(int nodes = 3000, int edges = 3000*3000/2): 
     nodes_(nodes+1), 
     edges_(edges), 
     dist_(nodes+1, max_int), 
     adjList_(nodes+1), 
     in_queue_(nodes+1, 0) 
    { 
    } 
    ~Graph() {} 
    void addEdge(int from, int to, int w) { 

     adjList_[from].emplace_back(ii(w, to)); 
     adjList_[to].emplace_back(ii(w, from)); 
    } 
    vii getNeighbours(int n) { 
     return adjList_[n]; 
    } 
    void dijkstra(int src); 

private: 
    vi dist_; 
    vector<vii> adjList_; 
    int nodes_; 
    int edges_; 
    int src_; 
    void print(int node); 
    vi in_queue_; 
    // queue<int> q_; 
    std::priority_queue<ii, vii, greater<ii>> q_; 
}; 

void Graph::dijkstra(int src) 
{ 
    src_ = src; 
    dist_[src] = 0; 
    q_.push(make_pair(0, src)); in_queue_[src_] = 1; 
    while(!q_.empty()) { 
     auto front = q_.top(); q_.pop(); 
     int d = dist_[front.second], u = front.second; 
     in_queue_[u] = 0; 
      for(int i = 0 ; i < (int)adjList_[u].size(); ++i) { 
       auto v = adjList_[u][i]; 
       if(dist_[v.second] > dist_[u] + v.first) { 
        dist_[v.second] = dist_[u] + v.first; 
        if(!in_queue_[v.second]) { 
         q_.push(make_pair(dist_[v.second], v.second)); 
         in_queue_[v.second] = 1; 
        } 
       } 
      } 
    } 

    for(int i = 1; i < nodes_; ++i) { 
     if(i == src_) { 
      continue; 
     } 
     if(dist_[i] == max_int) { 
      cout << "-1" << " "; 
     } 
     else{ 
      cout << dist_[i] << " "; 
     } 
    } 
    cout << endl; 
} 



int main(){ 
    std::ios::sync_with_stdio(false); 
    int t; 
    cin >> t; 
    for(int a0 = 0; a0 < t; a0++){ 
     int n; 
     int m; 
     cin >> n >> m; 
     unique_ptr<Graph> g(new Graph(n,m)); 
     for(int a1 = 0; a1 < m; a1++){ 
      int x; 
      int y; 
      int r; 

      cin >> x >> y >> r; 
      g->addEdge(x, y, r); 
     } 
     int s; 
     cin >> s; 
     //scanf("%d", &s); 
     g->dijkstra(s); 
    } 
    return 0; 
}