c++ - dijkstra 最短路径算法的时间复杂度是否取决于所使用的数据结构？

Question

存储图的一种方法是将节点实现为结构，例如

struct node {
int vertex; node* next; 
};

vertex 存储顶点编号，next 包含到另一个节点的链接。

我能想到的另一种方法是将其实现为 vector ，例如

vector<vector< pair<int,int> > G;

现在，在应用 Dijkstra 的最短路径算法时，我们需要构建优先级队列和其他所需的数据结构，如案例 2( vector 实现)。以上两种不同的图形应用方法在复杂度上会有什么不同吗？哪个更好？

编辑:在第一种情况下，每个节点都与可从给定节点直接访问的节点链表相关联。在第二种情况下，G.size() 是我们图中的顶点数G[i].size() 是从索引为 i 的顶点可直接到达的顶点数G[i][j].first 是从顶点 i 可达的第 j 个顶点的索引G[i][j].second 是从顶点 i 到顶点 G[i][j].first 的边的长度

Answer 1

两者都是adjacency list representations .如果正确实现，预计会导致相同的时间复杂度。如果你使用 adjacency matrix representation，你会得到不同的时间复杂度。 .

更详细 - 这归结为 the difference between an array (vector) and a linked-list .当您所做的只是遍历整个集合(即顶点的邻居)时，就像您在 Dijkstra 算法中所做的那样，这需要线性时间 (O(n))，无论您是否我们正在使用数组或链表。

运行 Dijkstra 算法的复杂性，如 Wikipedia 中所述, 会是
O(|E| log |V|) 在任何一种情况下都使用二进制堆。