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

Question

我尝试使用普通队列实现 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;
    }
}

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

Answer 1

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

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 Θ(V²) 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.

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

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

java

queue

graph

dijkstra

priority-queue