algorithm - 无优先队列无向循环图的Dijkstra算法实现

Question

我如何只使用队列而不是优先级队列来实现 Dijkstra 。这可能吗 ？如果不是，为什么？这是我在 java 中的代码..我的错误是什么？
“S”是起始节点 “W”是权重 “N”是矩阵的大小。我在 adj 矩阵的长度上加了 1，因为第一个节点是“1”。

这是来自 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]+" ");
        }
    }

}

Answer 1

是的，可以像那样实现它，但它不是最佳选择。 因为您使用队列而不是优先级队列，所以您可能必须多次展开图形的同一部分。因此，您将 logN 替换为 N^2 之类的东西(如果我没记错的话)。

如果您没有多次扩展节点(就像您在代码中所做的那样)，那么这是错误的，因为您使用的成本高于最小值。想象一下，您有 2 个节点，其直接链接的成本为 20，或者通过第三个节点的间接链接在两条边上的成本均为 1。假设最小距离为 20(因为它最先到达队列)，你会 expact 第二个节点，但如果你等待，你会找到成本为 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;
    }

根据问题陈述，两个节点之间可以有多个边。你只用最后一个。切换到最小值，你应该很好。