为了在未加权图上实现Dijkstra的最短路径算法，使其在线性时间内运行，应使用哪种数据结构？

Question

为了在未加权图上实现Dijkstra的最短路径算法以使其在线性时间内运行，要使用的数据结构为：

1. 队列
2. 堆
3. 堆
4. B树

我发现以下答案：

1. 队列，因为我们可以使用广度优先搜索（BFS）算法在未加权图中找到单个源最短路径，该算法使用“队列”数据结构，时间为O（m + n）（即相对于顶点和边的数量呈线性） ）

2. 要在线性时间内实现它，就需要一个最小堆，因为如果我们在此处删除一个最小堆中的节点，则将不需要任何时间进行调整，因为所有r具有相同的权重，因此删除一个节点需要O（1）。 n-1个节点，它将是O（n）。

有人可以解释哪个是正确的答案吗？

Answer 1

请注意，如果该图是未加权的，则不需要dijekstra，一个简单的BFS将在O（E + V）==>线性时间中完美运行。该算法的简单实现需要一个Queue Data Structure。