2022年数据结构程序_求有向图的最短路径文件 .pdf

《2022年数据结构程序_求有向图的最短路径文件 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构程序_求有向图的最短路径文件 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验课题有向图的路径问计师 1113012034 曹承2012.12.5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 问题描述：对于有向图 G= （V,E ） ，任意 Vi，Vj属于 V （Vi与 Vj 不等） ，判断从定点 Vi 到顶点 Vj是否存在路径。源程序实现：/* 求有向图的最短路径 */ #include #define n 5 #define e 7 typedef int vextype; typed

2、ef int adjtype; typedef struct vextype vexsn; adjtype arcsnn; graph; graph *ga; /* 建立 */ creatgraph() int i,j,k,w; printf(Please input:n); for(i=0;ivexsi); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - for(i=0;in;i+) for(j=0;jarcsij=1000;

3、 printf(Please input:n); for(k=0;karcsi-1j-1=w; printf(The result is:n); for(i=0;in;i+) for(j=0;jarcsij); printf(n); /* 求最短路径 */ DIJKSTRA() int Pn,Sn,Dn; int i,j,k,vl=0,pre; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - int min,max=1000,i

4、nf=8000; for(i=0;iarcsvli; if(Di!=max) Pi=1; else Pi=0; for(i=0;in;i+) Si=0; Svl=1; Dvl=0; for(i=0;in-1;i+) min=inf; for(j=0;jn;j+) if(!Sj)&(Djmin) min=Dj; k=j; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - Sk=1; for(j=0;jDk+ga-arcskj) Dj

5、=Dk+ga-arcskj; Pj=k+1; printf(length lujingn); for(i=0;in;i+) printf(%dt%d,Di,i+1); pre=Pi; while(pre!=0) printf(-%d,pre); pre=Ppre-1; printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - /* 主函数 */ void main() creatgraph(); printf(Dijkstra:n); DIJKSTRA(); getch(); 运行结果为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -