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

Question

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

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

我找到了以下答案：

一个队列，

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

线性时间需要一个最小堆

2. 来实现它，因为如果我们在这里删除最小堆中的一个节点，则调整不会花费任何时间，因为所有 r 都具有相同的权重，因此删除将花费一个节点的 O(1( .. 所以对于 n-1 节点，它将是 O(n(。

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

Answer 1

如果图形未加权，则不需要Dijkstra算法。一个简单的BFS将在O(E + V(时间复杂度(即线性时间复杂度(下完美工作。

该算法的简单实现需要队列数据结构。