实验三：贪心算法
单源最短路径问题
一、实验目的
（1）掌握贪心算法求解问题的一般特征和步骤；
（2）使用贪心算法编程，求解单源最短路径问题和多机调度问题。
二、实验内容/
单源最短路径问题，并对算法进行时间复杂性分析
二、设计分析
1.单源最短路径：即求源点到各个点之间的距离（间接达到或者直达）
2.迪杰斯特拉算法：选取一个源点 0，然后找距离源点最近的一个点 1，接着在
找距离 1 最近的点。
3.具体设计思路：首先，建立前驱数组 p[i],如果点与源点相连，将前结点设置为
源点，如果没有，则设置为-1。dis[i]存放每个结点到源点的距离。接着，寻找
距离源点最近的一个点，将次结点设置为 start 下次搜索的起始点。接着找距离
start 最近的点 j，判断次结点与源点有无直接路径，若有判断，路径长度，若满
足 dis[j]>dis[start]+c[start][j]，则将此节点作为新的 start。
4.时间复杂度分析：贪心法求解问题，时间复杂度与问题的规模相关。有两重
资源评论
