Chapter13-贪婪算法

《Chapter13-贪婪算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法2010年秋季授课教师：方芳授课班级：115091-3、114091班Chapter13贪婪算法内容提要13.1示例问题提出13.2贪婪算法的思想13.3贪婪算法的应用货箱装船拓扑排序单源最短路径最小耗费生成树2、单源点最短路径1、源点：路径上的第一个顶点；2、终点：路径上的最后一个顶点；3、最短路径：从源点到终点所经过的边上的权值之和为最小的路径。边上权值非负情形的单源最短路径问题【问题描述】给定一个带权有向图D和源点v，求从v到D中其余各顶点的最短路径——单源点的最短路径。问题针对有向图G，

2、每条边都有一个非负的长度（耗费）a[i][j]，路径的长度即为此路径所经过的边的长度之和。例给定如下带权有向图D，则从顶点1到其余顶点之间的最短路径如下表所示：4123651030102030510153015源点终点最短路径路径长度12<1,3,2>253<1,3>154<1,3,6,5,4>505<1,3,6,5>406<1,3,6>30单源最短路径示例：源点111111334234502346迪杰斯特拉算法求得的每一条最短路径必定只有两种情况：1）由源点直接到达终点，2）是只经过已经求得最短路径的顶点到

3、达终点（1）穷举法求出从源点到各个终点的所有路径，找出其中到各个终点的最短路径。（2）Dijkstar（迪杰斯特拉）算法Dijkstar提出按各条最短路径长度递增的顺序逐步产生最短路径。首先求出从源点v0到其余各顶点中长度最短的一条，然后参照它求出长度次短的一条最短路径，依此类推，直到从源点v0到其余各顶点的最短路径全部求出为止。如何求从某一源点到各个终点的路径?分步法求最短路径，每一步产生一个到达新的目的顶点的最短路径；Dijkstar算法的贪婪准则【贪婪准则】还未产生最短路径的顶点中，选择路径长度最短的目

4、的顶点——按路径长度顺序产生最短路径。利用数组p，前驱顶点p[i]给出从s到达i的路径中顶点i前面的那个顶点。从s到顶点i的路径可反向创建：从i出发按照p[i],p[p[i]],p[p[p[i]]],…的顺序，直到到达顶点s或0。算法实现：最短路径的存储p[1:5]=[0,1,1,3,4]。i=5开始，则顶点序列为p[i]=4，p[4]=3，p[3]=1=s，因此从1到5的路径：为1-3-4-5。辅助数组d[i]：顶点当前最短路径长度每个数组元素d[i]中存放：从源点s到终点i的当前最短路径长度。初始时，d[

5、i]=a[s][i]，即dist[i]的值为邻接矩阵a中第s行上各元素的值。a=4284513辅助数组d[i]的变化对所有未找到最短路径的顶点j，进行判断修改d[j]，使得d[j]=d[i]+a[i][j]if（d[j]>d[i]+a[i][j]）经过已经求得最短路径的顶点到达终点即d[j]=min{d[j],d[i]+a[i][j]}else不修改源点直接到达终点d[j]与d[i]+a[i][j]的大小L表源点未到达顶点表采用数据结构：无序链表VS.最小堆初始值：与源点邻

6、接的顶点链表更新情况：某个顶点j的d[j]发生变化，且不在L中，则加入到链表中Dijkstar算法伪代码（1）初始化d[i]=a[s][i]（1≤i≤n)对于邻接于s的所有顶点i，置p[i]=s，对于其余的顶点p[i]=0;对于p[i]≠0的所有顶点建立L表；（2）若L为空，终止，否则转至（3）（3）从L中删除d值最小的顶点，标识为i；（4）对于与i邻接的所有还未到达的顶点j，更新d[j]值为min{d[j],d[i]+a[i][j]}；若d[j]发生了变化且j还未在L中，则置p[j]=i，并将j加入L，转至

7、（2）。例终点从顶点1到各终点的d[i]值和最短路径12444324∞358866i3425S={1}{1,3}{1,3,4}{1,3,4,2}{1,3,4,2,5}a=428451313134121345Dijkstar算法（程序13-5）templatevoidAdjacencyWDigraph::ShortestPaths(ints,Td[],intp[]){if(s<1

8、

9、s>n)throwOutOfBounds();ChainL;/

10、/未到达顶点链表ChainIteratorI;//链表遍历器//initialized,p,andLfor(inti=1;i<=n;i++){d[i]=a[s][i];if(d[i]==NoEdge)p[i]=0;else{p[i]=s;L.Insert(0,i);}}a=4284513i12345d[i]428p[i]01101初始化d，p532N