Dijkstra算法實現無向優先隊列的無向循環圖

我如何實現Dijkstra只使用隊列而不是優先級隊列。這可能嗎？如果不是，爲什麼？這是我在Java中的代碼..最新我的錯誤？
「S」是起始節點「W」是權重「N」是矩陣的大小。自從第一個節點是「1」以來，我在adj矩陣的長度上加了1。Dijkstra算法實現無向優先隊列的無向循環圖

這是HackerRank鏈接了一個問題：https://www.hackerrank.com/challenges/dijkstrashortreach

import java.io.*; 
    import java.util.*; 

public class Solution { 

public static void main(String[] args) { 

    Scanner in = new Scanner (System.in); 
    int cases = in.nextInt(); 

    for(int i=0; i<cases; i++){ 
     int N = in.nextInt(); 
     int M = in.nextInt(); 
     int adj[][] = new int[N+1][N+1]; 

     for(int j=0; j<N+1; j++){ 
      for(int k=0; k<N+1; k++){ 
       adj[j][k] = 0; 
      } 
     } 

     for(int j=0; j<M; j++){ 
      int A = in.nextInt(); 
      int B = in.nextInt(); 
      int W = in.nextInt(); 

      adj[A][B] = W; 
      adj[B][A] = W; 
     } 

     int S = in.nextInt(); 

     Queue<Integer> que = new LinkedList<Integer>(); 
     que.add(S); 

     int dist[] = new int[N+1]; 
     Arrays.fill(dist,Integer.MAX_VALUE); 
     boolean vis[] = new boolean[N+1]; 

     dist[S] = 0; 
     vis[S] = true; 

     while(!que.isEmpty()){ 
      int q = que.poll(); 

      for(int j=1; j<=N; j++){ 
       if(!vis[j]&&q!=j && adj[q][j]!=0){ 

        if(dist[j]>dist[q]+adj[q][j]){ 
         dist[j] = dist[q]+adj[q][j]; 
         que.add(j); 
        } 
       } 
      } 
      vis[q] = true; 
     } 

     for(int j=1; j<=N; j++){ 
      if(dist[j]!=0) 
      System.out.print(dist[j]+" "); 
     } 
    } 

}

}

來源

2015-09-25 SSR

兩個明顯的問題是1.爲什麼你想要？ 2.什麼讓你覺得這是可能的？ –

是否可能。如果不是，你能解釋爲什麼。我只是好奇。謝謝 – SSR

@SSR Dijksrta的基礎是優先隊列。這就像要求實現合併排序而不合並。這是可能的，但結果可能完全是一種不同的算法。 – kajacx

是的，這是可以實現它這樣的，但它是不是最佳的。因爲您使用隊列而不是優先級隊列，您可能必須多次擴展圖形的相同部分。因爲你用N^2來代替logN（如果我沒搞錯的話）。

如果您不多次展開節點（就像您在代碼中做的那樣），那麼這是錯誤的，因爲您使用的成本高於最小值。假設您有兩個節點直接鏈接成本20或通過第三個節點的間接鏈接，兩邊的成本爲1。假設最小距離爲20（因爲它首先到達隊列中），您將擴展第二個節點，但是如果等待，則會找到成本爲2的路徑。如果尚不明顯，則向間接路徑添加更多節點。

至少做一個線性搜索找到最小值使其回到N（總體複雜度O（N^2）與您的設置）。最好的實現具有複雜度O（（N + M）logN）。

代碼中的另一個錯誤是在讀取數據：

for(int j=0; j<M; j++){ 
     int A = in.nextInt(); 
     int B = in.nextInt(); 
     int W = in.nextInt(); 

     adj[A][B] = W; 
     adj[B][A] = W; 
    }

根據問題的陳述，你可以有兩個節點之間的多條邊。你只使用最後一個。切換到最低限度，你應該很好。

來源

2015-09-25 11:55:30 Sorin

非常感謝我終於搞定了！你是最好的！ – SSR

Dijkstra算法實現無向優先隊列的無向循環圖

回答

相關問題