单源最短路径的贪心算法.doc

《单源最短路径的贪心算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二、实习过程:1、贪心算法思想：当一个问题具有最优子结构性质时，可用动态规划法求解。但有时用贪心算法会更简单、更有效。贪心算法总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。2、单源最短路径问题：给定带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。2、解单源最短路径问题算法：Dijkstra算法是解单源最短路径的贪心算法。

2、其基本思想是，设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路径称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路径长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。直到S包含了所有V中的顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。4、Dijkstra算法描述：输入带权有向图是G=（V，

3、E），V={1,2，...，n}。顶点v是源。a是一个二维数组，a[i][j]表示边（i，j）的权。当（i，j）不属于E时，a[i][j]是一个无穷大的数。publicstaticvoiddijkstra(intv){//单源最短路径问题的Dijkstra算法intn=dist.length-1;if(v<1

4、

5、v>n)return;boolean[]s=newboolean[n+1];//初始化for(inti=1;i<=n;i++){dist[i]=a[v][i];s[i]=false;if(dist[i]<0)prev[i]

6、=0;elseprev[i]=v;}dist[v]=0;s[v]=true;for(inti=1;i0)){u=j;temp=dist[j];}s[u]=true;for(intj=1;j<=n;j++){if((!s[j])&&(a[u][j]>0)){intnewdist=dist[u]+a[u][j];if(newdist

7、[j]

8、

9、dist[j]==-1){dist[j]=newdist;prev[j]=u;}}}}}三、实习总结：通过本次实习，对贪心算法可求解的问题有了进一步了解，有利于区分何种情况下用动态规划，何种情况用贪心算法，对确定何时用贪心算法可以得到问题的整体最优解提供了帮助，同时也为以后解题带来便利。