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

Question

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

这是来自 HackerRank Link 的问题：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 个节点，其直接 link 的成本为 20，或者通过第三个节点的间接 link 在两条边上的成本均为 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;
    }

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

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

Dijkstra's algorithm implementation for undirected cyclic graphs without priority queues

algorithm

queue

shortest-path