1.算法处理要求

要求图中不能有负权值的边存在
如果想处理有负权值的图，可以参见
Bellman-Ford最短路径算法

2.算法思想

2.1
**dist[]**数组记录当前源点到定点的最短路径的已经计算出来的最短路径的值.
**parent[]**用来标记已经确定最短路径的点的集合和未确定最短路径的点集。
**track[]**用来记录在更新过程中的路径信息，只需要记录节点的前驱节点就行了。
2.2在大循环中，首先找到未被访问过的并且是dist[]中值最小的一个点，把该点的parent设置访问过，然后以该点为发散点，进行该点的全部邻接点的访问，访问条件是邻接点也是未被其他点访问过的。然后比较，如果邻接点的dist>该点dist + 该点与此邻接点的距离，则更新dist[临接点]，更新parent[邻接点]。。

3.算法伪代码

//****************初始化工作
for all v in V:
{dist[v] = IFN(无穷大);parent[v] = 0;//0表示未访问track[v] = 0;//记录节点的前置节点的情况
}
visited[s] = 0;	
dist[s] = 0;
track[s] = s;
//***************运行工作
for i=1 <= |V|
{1.在dist[]中找未被访问过的并且dist[]值最小的点cv（current vertex）2.visited[cv] = 1;3.对cv的所有邻接点w（一个循环），先认证这个点有没有被访问过if(!visited[w]){再判断节点距离是否可以通过经过cv缩短if( dist[w] > dist[cv] + lenth(cv,w) ){dist[w] = dist[cv] + lenth(cv,w);track[w] = cv;}}
}
注意一下visited和track更新的地方不一样！！！！！！！！！！！！！

4.算法优化

1. c++中优先队列可以对入队的信息进行排序，并且优先队列是用堆实现的，复杂度低因此，可以省去遍历dist[]数组来直接得到源点到定点最小距离是哪个定点。
2. 算法伪代码

mainfor all v in V：{dist[v] = M(a large enough number);parent[v] = 0;}dist[s.ver] = 0;parent[s.ver] = s;Q.push(s);//这里s应该是一种含有源点到该点距离和该点是那个点的信息的结构体。可以用c++中的pair实现while(!Q.empty){P = Q.top();//每次出队列的就是最小的那个路径Q.pop();v = P.ver;if(dist[v] < v.dis) continue;//用来优化遇见旧的点的情况for all neighbors w of v{if(dist[w]>dist[v]+length(v,w)){parent[w] = v;dist[w] = dist[v]+length(v,w);Q.push(make_pair(dist[w],w));}}}**最终结果：parent数组中存放了路径信息dist数组中存放了路径长短信息**

Dijkstra和BFS多像啊，尤其是其中的那个入队操作
其实Dijkstra也是散发型的向外部寻找点，也就是BFS的升级版。

5.算法性能

用不同的数据结构实现的是后，时间复杂度不一样

1. 邻接数组（n^2）
2. 优先队列（m*logn）