Dijkstra算法时间复杂度

Question

我只知道是O(n2)，不知道怎么算来的，请详细讲一下。

网上一搜全都是这句话：
Dijkstra 算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合 Q，所以搜索 Q 中最小元素的运算（Extract-Min(Q)）只需要线性搜索 Q 中的所有元素。这样的话算法的运行时间是 O(n2)。

没说怎么得到这个n2的.

附算法：
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G]
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0
6 S := empty set
7 Q := set of all vertices
8 while Q is not an empty set
9 u := Extract_Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[v] > d[u] + w(u,v)
13 d[v] := d[u] + w(u,v)
14 previous[v] := u

Answer 1

我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。

Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。

对于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。相关问题和算法

在Dijkstra算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图的一系列次短路径。

OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。
与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。

与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。

如果有已知信息可用来估计某一点到目标点的距离，则可改用A*算法，以减小最短路径的搜索范围。

Answer 2

推荐看下例子
里面有关于Dijkstra，可以真实的跑一下com.algorithm.test.ProgramTest##getShortestDistanceFromAToB
再看代码：里面for循环中出现for循环，所以时间复杂度O(n^2)

Answer 3

行2--4的初始化对n个顶点进行，显然是O（n）
5--6行O（1）
7行n个顶点入队列O（n）
8行--14行，从8行可以看出进行了n遍循环，每遍在第九行调用一次ExtractMin过程，ExtractMin过程需要搜寻邻接表，每一次需要搜寻整个数组，所以一次操作时间是O(n);11行到14行对节点u的邻接表中的边进行检查，总共有|E|次（总共.每条边最多检查一次)，因此是O(E)；合起来就是O（E+n*n） = O（n^2);

以上合起来就是O（n）+O（1）+O（n）+O（n^2） == O（n^2).

就这样本回答被提问者采纳