对于具有v顶点和e边线且边缘存储在二进制最小堆中的图，最坏情况下的运行时间是O((n+e)lg(n))。但是，这是假设我们使用邻接链表来表示图。使用邻接矩阵需要O(n^2)遍历，而可以在中遍历链接列表表示形式O(n+e)。
因此，使用矩阵表示图是否会将Dijkstra的运行时间更改为O(n^2lg(n))？
在O（log n）的成本被支付用于处理边缘，而不是为步行的图表中，所以如果知道在图中边的实际数目则Dijkstra的与最小堆邻接矩阵算法是内为O（n ^ 2 + （n + e）log（n））时间。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句