dijkstra算法是计算有向图中最短路径的算法。这个算法我很有印象。

在我高二的时候，某个星期天下午考NOIP，上午我才开到了这个算法。

然后将大意记住了，最后成功在下午的考试中遇到了使用这个算法的题，并快速算出来了结果。

这个算法的要求是图中的路径的权重不能有负数。

算法：

可以理解为运动员接力赛跑，好几个运动员从起点开始跑，分别朝着与起点连接的那几个顶点。假设所有运动员的速度都是一样的。

那么朝着距离最近的顶点方向跑的运动员会最先到达那个顶点，之后这个顶点再派出其他运动员，朝着与这个顶点相连接的其他顶点跑。而其他距离起点比较远的顶点必须等待相应的运动员到达该顶点之后才能派出其他运动员。

这样循环下去，最先到终点的那个运动员所接力得到的路径肯定是最短路径。

1. 从开始顶点，遍历所有与其相邻的顶点。
2. 找到：与开始顶点距离最短的点 而且没有被遍历过的点。
3. 将这个点标记为遍历过。
4. 然后遍历这个点。重复方法1.

伪代码：

[code lang=”c”]Dijkstra() {
初始化;
for(循环n次) {
u = 使dis[u]最小的还未被访问的顶点的编号;
记u为确定值;
for(从u出发能到达的所有顶点v){
if(v未被访问 && 以u为中介点使s到顶点v的最短距离更优)
优化dis[v];
}
}
}[/code]

相关资料参考

《算法基础:打开算法之门》

《算法导论》
http://blog.csdn.net/liuchuo/article/details/52300011
http://www.cnblogs.com/iambupu/p/5713952.html