精选优质文档-倾情为你奉上单源最短路径计科1班 朱润华 方法1：贪心算法一、 贪心算法解决单源最短路径问题描述：单源最短路径描述：给定带权有向图G=(V,E),其中每条边的权是非负实数。另外，还给定V中的一个顶点，称之为源(origin)。现在要计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是到达路径各边权值之和。Dijkstra算法是解决单源最短路径问题的贪心算法。Dijkstra算法的基本思想是：设置顶点集合S并不断地做贪心选择来扩充集合。一个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。贪心扩充就是不断在集合S中添加新的元素（顶点）。初始时，集合S中仅含有源(origin)一个元素。设curr是G的某个顶点，把从源到curr且中间只经过集合S中顶点的路称之为从源到顶点curr的特殊路径，并且使用数组distance记录当前每个顶点所对应的最短路径的长度。Dijkstra算法每次从图G中的(V-S)的集合中选取具有最短路径的顶点curr，并将curr加入到集合S中，同时对数组distance进行必要的修改。一旦S包含了所有的V
