Dijkstra算法

2017年03月09日 12点热度 0人点赞 0条评论
Dijkstra算法是一个经典的算法——他是荷兰计算机科学家Dijkstra于1959年提出的单源图最短路径算法,也是一个经典的贪心算法。所谓单源图 是规定一个起点的图,我们的最短路径都是从这个起点出发计算的。算法的适用范围是一个无向(或者有向图),所有边权都是非负数。

算法描述:

节点集合V = {}空集合,距离初始化。
节点编号0..n – 1, 起点编号0≤ s < n。

距离数组
起点 d[s] = 0
其他 d[i] = ∞, 0 ≤ i < n,  i ≠ s。
循环n次

找到节点i 不属于 V,且d[i]值最小的节点i。

V = V + i

对所有满足j  V的边(i, j) 更新d[j] = min(d[j] , d[i] + w(i,  j))。

最后,我们来提供输入输出数据,由你来写一段程序,实现这个算法,只有写出了正确的程序,才能继续后面的课程。
未经允许不得转载!Dijkstra算法

update

纸上得来终觉浅, 绝知此事须躬行。