为什么即使我使用简单队列而不是优先级队列,Dijkstra 实现仍然有效?

Why is the Dijkstra Implementation working even if I use Simple Queue instead of priority queue?

我尝试使用普通队列实现 Dijkstra,每当我放松边缘时,我都会将该顶点添加到队列中,这里是 java

中的实现
import java.util.*;

public class Main 
{
    static HashMap<Integer, List<Edge>> graph = new HashMap<>();
    public static void main(String[] args)
    {
        graph.put(0, (List<Edge>)Arrays.asList(new Edge[]{
            new Edge(0, 1, 5),
            new Edge(0, 2, 2),
        }));
        graph.put(1, (List<Edge>)Arrays.asList(new Edge[]{
            new Edge(1, 3, 1),
        }));
        graph.put(2, (List<Edge>)Arrays.asList(new Edge[]{
            new Edge(2, 1, 1),
            new Edge(2, 3, 7),
        }));
        graph.put(3, (List<Edge>)Arrays.asList(new Edge[]{}));
        Integer[] dist = dijkstra(graph, graph.size(), 0);
        for(int i = 0;i < dist.length;i++)
        {
            System.out.print(" " + dist[i]);
        }
    }
    public static Integer[] dijkstra(HashMap<Integer, List<Edge>> graph, int numNodes, int start)
    {
        Integer[] dist = new Integer[numNodes];
        for(int i = 0; i < dist.length;i++)
        {
            dist[i] = Integer.MAX_VALUE;
        }

        LinkedList<Integer> queue = new LinkedList<Integer>();

        dist[start] = 0;
        queue.add(start);
        while(queue.size()!=0)
        {
            Integer current = queue.poll();
            List<Edge> edges = graph.get(current);
            for(Edge e : edges)
            {
                if(dist[e.from] + e.weight < dist[e.to])
                {
                    dist[e.to] = dist[e.from] + e.weight;
                    queue.add(e.to);
                }
            }
        }

        return dist;
    }
}

class Edge
{
    int from, to, weight;
    Edge(int from, int to, int weight)
    {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

如您所见,只要有松弛,我就会将顶点添加到队列中。 我的问题是这是正确的实现,我的意思是它在所有情况下都有效吗?它比优先级队列有什么缺点?

可能你应该不错;不使用优先队列只会影响效率

Wikipedia:

While the original algorithm uses a min-priority queue and runs in time Θ((V+E)logV) (where V is the number of nodes and E is the number of edges), it can also be implemented in Θ(V2) using an array.

Breadth-first search can be viewed as a special-case of Dijkstra's algorithm on unweighted graphs, where the priority queue degenerates into a FIFO queue.