使用邻接矩阵和邻接链表时，Dijkstra算法的时间复杂度对比

Question

对于一个有 v 个顶点和 e 条边以及在二进制最小堆中存储的边缘（fringe）的图形，最坏情况的运行时间为 O((n+e)lg(n))。然而，这是假定我们使用邻接链表来表示图形的情况下。使用邻接矩阵需要 O(n^2) 的时间来遍历，而链表表示法可以在 O(n+e) 的时间内遍历。

因此，使用矩阵来表示图形是否会改变 Dijkstra 算法的运行时间为 O(n^2lg(n)) 呢？

- Abhishek Patel

Answer 1

在处理边的时候，需要付出O(log n)的代价，而不是在遍历图时。因此，如果您知道图中实际的边数，则使用邻接矩阵和最小堆的Dijkstra算法时间复杂度为O(n^2 + (n+e)log(n))。

- Matt Timmermans