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算法实现无向优先队列的无向循环图

回答

相关问题