基本信息

---

下载

文档摘要

---

斯特拉（）算法是求解最短路径问题的算法，可以求得从起点到终点的路

径中权重总和最小的那条路径路径。

如果我们想求出起点到一个点的最短路径，必然要先求出中转点的最短路径，

也就是说，如果起点到某一点的最短路径要经过中转点，那么中转点

一定是先于被确定的最短路径的点。

设起点为，表示从到的最短路径，为的前驱节点，用来输出路径。

初始化：dis[v]=∞(v≠s

在没有被过的点中找一个顶点使得是最小的。

标记为已确定最短路径

与相连的每个未确定最短路径的顶点