Dijkstra算法

参考资料：
1. 图论之Dijkstra最短路径算法
2. Dijkstra算法时间复杂度

基本思路：
维护一个从V0到其他顶点的距离，每次选择最近的一个顶点V1，然后把跟V1相连的顶点的距离修正下，看能不能通过V1缩短V0到其他点的距离。

好好理解下这段话

想法简单，但关键是怎么按照“客观存在的大小顺序”计算各点到源点v的距离呢？我们先简单思考一下，按照距离v的远近顺序，v一定是排第一的，然后呢，排第二的一定是和v直接相连的点吧，否则总有一个点介于排第二的点和v之间，而它到v的距离肯定也比第二到v的距离近，那这个第二就有些名副其实了。比较麻烦的是，排第三的点在哪里？利用递归的想法就会发现，排第三的点应该从那些和v直接相连，或者和第二名直接相连的点中去寻找，否则第三名就会名副其实了。总结一下，需要找第n个点时，只需要在那些和前n-1个点直接相连的点里面找就行了。

复杂度

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：
行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).