单源顶点最短路径问题设计.doc

1、软件工程设计报告题目：单源顶点最短路径问题设计报告科系：计算机科学与技术班级：姓名：学号：设计报告分析：报告内容分为四大部分：1) 课程设计的需求和规格说明：包括描述问题，简述题目要解决的问题是什么；规定软件做什么；原题条件不足时补全。2) 设计：（概要设计和详细设计）设计思想：存储结构（题目中限定的要复述）；主要算法基本思想。不要画框图。设计表示：每个函数声明和规格说明；列出每个函数所调用和被调用的函数，也可以通过调用关系图表达。实现注释：各项功能的实现程度；在完成基本要求的基础上还实现了什么功能。3) 调试报告：调试过程中遇到的主要问题是如何解决的；对设计和编码的回顾讨论和分析；时间复杂度

2、、空间复杂度分析；改进设想；经验和体会等。4) 附录：源程序清单和结果：源程序要加注释，除原有的注释外还可以再用笔加一些必要的注释。如果题目规定了测试数据，则结果要包含这些测试数据和运行输出结果，当然还要包含其它测试数据及其运行输出（有时需要多组数据）。报告正文：1、问题描述用邻接矩阵costnn表示一个有向网，若costij=0，则表示顶点i和j为同一个顶点；若costij=，则表示顶点i和j无边；若costij=Wij，则表示顶点i和j有边，其权值为Wij。试求出从有向网的某一顶点（称源点）出发到其余各顶点的最短路径。2、基本要求程序能够求出源点到其余各顶点间的一条最短路径。1需求与规格说

3、明 对用邻接矩阵表示的有向图，从某一顶点出发（称为源点）到该图其它各顶点（称为终点）有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵costnn中的每一个元素只能有三种情况： 当i=j时，costij=0； 当顶点i和j无边时，costij=； 当顶点i和j有边，且其权值为Wij时，costij=Wij。由于题目中没有规定输出格式，此程序以顶点序号的形式将最短路径输出到终端上去，并输出该最短路径的长度。2设计1）设计思想（1）存储结构。以邻接矩阵存储有向网，如图一所示，其邻接矩阵为cost。 自己输入一个矩阵 邻接矩

4、阵 图一 有向网G及其邻接矩阵cost有向图的邻接矩阵costij定义如下： int costij;（2）主要算法基本思想。单源最短路径问题采用迪杰斯特拉（Dijkstra）提出的按路径长度递增的次序产生最短路径的算法。此算法把网中所有的顶点分成两组，分别用S和T表示。凡是以i0为源点，已经确定了最短路径的终点属于第一组S，S的初态应只包含i0。另一组T则是尚未确定最短路径的顶点集合。T的初态应是除源点外的网中所有顶点的集合，按各顶点与i0间的最短路径的长度递增的次序，逐个把T中的顶点加入到S中，使得从i0到S中各顶点的路径长度始终不大于从i0到T中各顶点的路径长度。它的初始状态即是邻接矩阵c

5、ost中第i0列内各列的值。显然，从源点到各顶点的最短路径中最短的一条路径应为 distv=mindisti(i=1,2,n)第一次求的最短路径长度必然是(i0,v)，这时顶点号v应从T中删除而并入S。每当选出一个顶点号v并使之并入S后，就要修改T中各顶点的最短路径长度dist。对于T中的某一个顶点i来说，其最短路径长度或者仍是(i0,i)，或者是(i0,v,i)，决不可能有其它选择，也就是说，若distv+costvidisti 则修改disti，使disti= distv+costvi当T组中各顶点的dist进行修改后，再从中挑选出一个路径长度路径最小的顶点，从T中删除后再并入S。依次类推

6、，就能求出所需的最短路径长度。其中dist、S、pre都定义为整型数组，数组S用以标记那些已经找到最短路径的顶点。若Si为1，表示已找到源点到顶点i的最短路径；若Si为0，则表示从源点到顶点i的最短路径尚未求得。Pre i表示从源点到顶点i的最短路径上该点的前趋顶点，若从源点到顶点无路径，则用0用为其前一个顶点序号。2）设计表示法（1）函数调用关系如图二所示。 main() mixpath（2）函数接口说明Void mainpath(int n,int cost,int i0,int dist,int pre);/*求n个顶点，邻接矩阵为cost，从源点i0到各顶点的最短路径，dist记载从源

7、点到其余各顶点的最短路径长度，pre记载从源点到其余各顶点的最短路径。其中指针*pd、*pp分别指向数组dist和pre */3）实现注释l 系统限定邻接矩阵的阶n不超过20；l 为方便起见，系统假设有向网中边的权为整型数；l 若有向网中顶点i到j之间无边，则取值32767。4）详细设计Dijkstra算法描述如下：（1） 输入顶点个数n、邻接矩阵cost和源点序号i0；（2） 送初值：将i0加入第一组S；令disti=costi0i；(i=1,2,n)；（3） 重复n-1次做： 在不属于S的顶点U中，选取具有最小distu值的顶点v； 将v加入S； 对不属于S的顶点U做distu=mindi

8、stu, distv+costvu;/* distu取distu, distv+costvu两个数中的最小值*/（4） 输出各最短路径的长度disti及相应的最短路径pre。3调试报告在调试过程中要特别注意函数调用时参数的传递问题，用数组名作为参数可进行传值调用，因而可将函数中的运行结果传递给主调函数，得出正确结果；再一个要注意的是输出结果时，循环结束的条件应为：k=i0或k=0时退出循环，否则将出现死循环。另外，上机前的静态检查不能忽视；程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况并对程序规格说明作少量调整和改动。求单源最短路径的具体步骤将图G中所有的顶点V分成两个顶点集

9、合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合求单源最短路径的具体步骤1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以就要用一个记录从源点v到其它各顶点的路径长度数组dist,开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。设一个用来记录从源点到其它顶点的路径数组path,path中存放路径上第i个顶点的前驱顶点）2、在上述的最短路径dist中选一条最短的，并将其终点（即）k加入到集合s中3、调整T中各顶点到源点v的最短路径。 因为

10、当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是取distk+gk,jdistj与distj的较小者4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点Program Dijkstra; ConstMaxP=5;Infinity =MaxLongInt; M = MaxLongInt; map : Array 1.5,1.5 Of LongInt = (M ,10 ,M ,30 ,100), (M ,M ,50 ,M ,M ),

11、 (M ,M ,M ,M ,10 ), (M ,M ,20 ,M ,60 ), (M ,M ,M ,M ,M ); Var map : Array 1.MaxP, 1.MaxP Of LongInt; 邻接矩阵, Infinity表示没有边相连 path : Array 1.MaxP Of LongInt; 路径数组, 记录从源点出发的具体最短路径 source : LongInt; 源点变量 Procedure Dijkstra; Var dist : Array 1.MaxP Of LongInt; 距离数组, 记录目前从源点出发已经找到的最短路径长度 Visited : Array 1.

12、MaxP Of Boolean; 标志数组, 记录是否已经找到了某一点的最终最短路径 i, j, min, minp : LongInt; Begin FillChar(Visited, SizeOf(Visited), false); 初始化源点和路径数组 For i:=1 To MaxP Do Begin dist:=mapsource,i; If distM Then path:=source Else path:=0; End; 源点的最短路径肯定是不用找的. Visitedsource:=True; Dijkstra的思想是按递增长度来产生路径, 每次选出当前已经 找到的最短的一条路

13、径, 它必然是一条最终的最短路径. 因此 每次找出当前距离数组中最小的, 必然是一条最终的最短路径 For i:=2 To MaxP Do Begin min:=Infinity; minp:=0; For j:=1 To MaxP Do If (NOT Visitedj) AND (distjmin) Then Begin min:=distj; minp:=j; End; 已找到源点到点minp的最短路径, 做上标志 Visitedminp:=True; 修改距离数组 For j:=1 To MaxP Do If (NOT Visitedj) AND (distminp+mapminp,j

14、distj) ThenBegin distj:=distminp+mapminp,j; pathj:=minp; End; End; End;4程序代码1#include #include #define MAX 10000#define MAXLEN 40#define VEXTYPE int#define ADJTYPE inttypedef struct VEXTYPE vexsMAXLEN; /顶点的信息 ADJTYPE arcsMAXLENMAXLEN;/邻接矩阵 int vexnum,arcnum ; /顶点数和边数 int kind; /有向网的kind=3 MGRAPH;MGR

15、APH create_mgraph()/*建立有向网的邻接矩阵结构*/int i, j, k, h; MGRAPH mg; mg.kind = 3; printf(nn输入顶点数和边数(用逗号隔开) : ); scanf(%d,%d, &i,&j); mg.vexnum = i; /*存放顶点数在mg.vexnum中 */ mg.arcnum = j; /*存放边点数在mg.arcnum中*/ fflush(stdin); for(i = 0; i mg.vexnum; i+) printf(输入顶点 %d 的值 : ,i + 1); /*输入顶点的值*/ scanf(%d, &mg.vexs

16、i); fflush(stdin); for(i = 0; i mg.vexnum; i+) /*邻接矩阵初始化*/ for(j = 0; j mg.vexnum; j+) mg.arcsij = MAX; for(k = 1; k = mg.arcnum; k+) printf(输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): ,k); scanf(%d,%d,&i,&j); /*输入弧的起始顶点和终止顶点*/ fflush(stdin); while(i mg.vexnum | j mg.vexnum) printf(输入错，重新输入: ); scanf(%d,%d, &i, &j)

17、; printf(输入此边权值 : ); /*输入弧上之权值*/ scanf(%d, &h); mg.arcsi - 1j - 1 = h; return mg;main() MGRAPH mg; int costMAXLENMAXLEN; int pathMAXLEN, sMAXLEN; int distMAXLEN; int i, j, n, v0, min, u; printf(n求有向图单源点最短路径n); mg = create_mgraph(); /*建立有向图的邻接矩阵结构*/ printf(nn起始顶点为 : ); /*有向图中顶点的编号从1编起*/ scanf(%d, &v0

18、); v0 -; n = mg.vexnum; for(i = 0; i n; i+) /*cost矩阵初始化*/ for(j = 0; j n; j+) costij = mg.arcsij; costii = 0; for(i = 0; i n; i+) disti = costv0i; /*dist数组初始化*/ if(disti 0) /*path数组初始化*/ pathi = v0; for(i = 0; i n; i+) /*s数组初始化*/ si = 0; sv0 = 1; for(i = 0; i n; i+) /*按最短路径递增算法计算*/ min = MAX ; u = v

19、0; for(j = 0; j n; j+) if(sj = 0 & distj min) min = distj; u = j; su = 1; /*u顶点是求得最短路径的顶点编号*/ for(j = 0; j n; j+) if(sj = 0 & distu + costuj distj)/*调整dist*/ distj = distu + costuj; pathj = u; /*path记录了路径经过的顶点*/ for(i = 0; i n; i+) /*打印结果*/ if(si = 1) u = i; while(u != v0) printf(%d - , u + 1); u =

20、pathu; printf(%d , u + 1); printf( d = %dn, disti); /*有路径*/ else printf(%d - %d d= MAXn , i + 1, v0 + 1);/*无路径*/printf(nn); 程序代码21. #include 2. #include 3. #include 4. 5. usingnamespacestd; 6. 7. typedefstruct 8. intvexs10; 9. intedges1010; 10. intn; 11. inte; 12. MGraph; 13. 14. #defineINFINITE2048

21、 15. 16. voidCreateGraphM(MGraph*G) 17. 18. intN1,N2; 19. inti,j,k; 20. 21. coutEnterthenumberofvertexsandedges:(G-n)(G-e); 23. k=G-n; 24. 25. for(i=0;i(G-vexsi); 27. 28. for(i=0;in;i+) 29. for(j=0;jn;j+) 30. G-edgesij=INFINITE; 31. 32. 33. coutEDGES:endl; 34. 35. for(k=0;ke;k+) 36. intweight; 37. c

22、inN1N2weight; 38. G-edgesN1-1N2-1=weight; 39. 40. 41. return; 42. 43. 44. typedefstruct 45. intvisited10; 46. intfinishing_time10; 47. intdiscovery_time10; 48. inttimes; 49. DFS_DATA; 50. 51. typedefstruct 52. intweight; 53. intparent; 54. STORE; 55. 56. voidDFSM(MGraph*G,intindex,DFS_DATA*DATA) 57.

23、 58. DATA-times+; 59. 60. DATA-discovery_timeindex=DATA-times; 61. 62. DATA-visitedindex=1; 63. 64. for(inti=0;in;i+) 65. if(G-edgesindexi=1&DATA-visitedi=0) 66. DFSM(G,i,DATA); 67. 68. 69. DATA-finishing_timeindex=DATA-times; 70. DATA-times+; 71. 72. 73. voidDFS(MGraph*G,DFS_DATA*DATA) 74. 75. for(

24、inti=0;in;i+) 76. DATA-visitedi=0; 77. 78. 79. for(inti=0;in;i+) 80. DATA-finishing_timei=0; 81. DATA-discovery_timei=0; 82. 83. 84. DATA-times=0; 85. 86. for(inti=0;in;i+) 87. if(DATA-visitedi=0) 88. DFSM(G,i,DATA); 89. 90. 91. 92. vectorTopological_Sort(MGraph*G) 93. 94. DFS_DATA*DATA=newDFS_DATA;

25、 95. 96. vectorRESULT; 97. vectortmp; 98. 99. DFS(G,DATA); 100. 101. for(inti=0;in;i+) 102. tmp.push_back(DATA-finishing_timei); 103. 104. sort(tmp.begin(),tmp.end(); 105. 106. for(inti=G-n-1;i=0;i-) 107. for(intj=0;jn;j+) 108. if(DATA-finishing_timej=tmpi) 109. RESULT.push_back(j); 110. 111. 112. d

26、eleteDATA; 113. 114. returnRESULT; 115. 116. 117. intAcyclic(MGraph*G) 118. 119. vectorCHECK; 120. 121. CHECK=Topological_Sort(G); 122. 123. for(inti=1;in;i+) 124. for(intj=0;jedgesCHECKiCHECKj=1) 127. return1; 128. 129. 130. return0; 131. 132. 133. vectorCritical_Path(MGraph*G,intfrom) 134. 135. ve

27、ctorS(G-n); 136. 137. if(Acyclic(G)=1) 138. gotoNegacyclic; 139. 140. for(inti=0;in;i+) 141. Si.weight=INFINITE; 142. Si.parent=-1; 143. 144. 145. Sfrom.weight=0; 146. Sfrom.parent=from; 147. 148. for(inti=0;in)-1);i+) 149. for(intj=0;jn;j+) 150. for(intk=0;kn;k+) 151. if(G-edgesjkSj.weight-G-edgesj

28、k) 154. Sk.weight=Sj.weight-G-edgesjk; 155. Sk.parent=j; 156. 157. 158. 159. for(inti=0;iS.size();i+) 160. Si.weight=abs(Si.weight); 161. 162. returnS; 163. 164. Negacyclic: 165. coutThereisNegacyclicendl; 166. S.resize(0); 167. returnS; 168. 169. 170. voidPrint_Path(vector&S,intindex) 171. if(index

29、=0) 172. coutindex+1; 173. return; 174. 175. else 176. Print_Path(S,Sindex.parent); 177. coutindex+1; 178. 179. 180. return; 181. 182. 183. 184. intmain() 185. 186. vectorS; 187. MGraph*G=newMGraph; 188. 189. CreateGraphM(G); 190. S=Critical_Path(G,0); 191. 192. coutendl; 193. 194. intMAX=0; 195. in

30、tindex; 196. for(inti=0;iS.size();i+) 197. if(MAX=Si.weight) 198. MAX=Si.weight; 199. index=i; 200. 201. 202. Print_Path(S,index); 203. 204. coutendlendl; 205. 206. for(inti=0;iS.size();i+) 207. couti+1; 208. coutSi.weight; 209. coutSi.parent+1; 210. coutendl; 211. 212. deleteG; 213. 214. return0; 215. 5结果分析对图一的有向网，执行情况如下：输入：备注（作者根据自己的实际情况输入数据）输入结束后，程序执行并显示输出计算结果如下：备注（与上步输入有关）本文是通过网络收集的资料，如有侵权请告知，我会第一时间处理。 .