狄克斯特拉算法（Dijkstra's Algorithm)

本课程是从少年编程网转载的课程，目标是向中学生详细介绍计算机比赛涉及的编程语言，数据结构和算法。编程学习最好使用计算机，请登陆 www.3dian14.org (免费注册，免费学习)。

狄克斯特拉算法是一种常见的花心，额，贪心算法，今天给孩子演示该算法，发现网上的动图都不尽人意，就动手修了个图。

算法过程是：在已经开拓的疆域的边缘，找出最美好的节点，更新该节点芳邻们的开销。然后重复这个过程，直到天长地久。

动图比较长，分成三部分：

---

上面的算法过程只计算了各个节点到初始节点的距离，要回溯出最短路径，我们需要维护一个节点到父节点的表。（父节点是计算该节点开销时的前序节点，父节点的信息在不断更新中）

节点	父节点
a	s

Dijskstra算法中贪心的正确性证明，用到图论中的一个小定理，请用反证法证明一下。

引理：最短路径的子路径本身就是最短路径

（提示：如果s->z不是最短路径，那么存在。。。）