离散数学.docx
- 文档编号:5523489
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:12
- 大小:110.38KB
离散数学.docx
《离散数学.docx》由会员分享,可在线阅读,更多相关《离散数学.docx(12页珍藏版)》请在冰点文库上搜索。
离散数学
离散数学——最小路径问题及其编程求解
一、实验目的
通过本次实验的学习,理解最小路径问题及其编程求解.
二、实验内容
用C语言编程实现求赋权图中任意两点间最短路径的Floyd算法,并能对给定的两结点自动求出最短路径。
三、使用环境
设备:
PC机
操作系统:
Windows
编译软件:
visualC++6.0
四、源代码及调试过程
节点1到其余个点的最短路径长度,并输出
#include
#definemaxsize1000//表示两点间不可达,距离为无穷远
#definen6//结点的数目
voiddijkstra(intC[][n],intv);//求原点v到其余顶点的最短路径及其长度
voidmain()
{
FILE*fp=NULL;
fp=fopen("output1.txt","w");
if(fp==NULL)
{
printf("打开文件失败,程序退出!
\n");
}
fprintf(fp,"——Dijkstra算法——\n");
intC[n][n]={
{maxsize,maxsize,15,maxsize,maxsize,maxsize},
{20,maxsize,maxsize,maxsize,10,30},
{maxsize,4,maxsize,maxsize,maxsize,10},
{maxsize,maxsize,maxsize,maxsize,maxsize,maxsize},
{maxsize,maxsize,maxsize,15,maxsize,maxsize},
{maxsize,maxsize,maxsize,4,maxsize,10}
},v=1,i,j;
fprintf(fp,"【打印有向图的邻接矩阵】\n");
for(i=0;i { for(j=0;j { fprintf(fp,"\t%d",C[i][j]); } fprintf(fp,"\n"); } fprintf(fp,"【打印原点1到其他各点的最短路径及其长度】\n"); if(fp) { fclose(fp); fp=NULL; } dijkstra(C,v); printf("文件已写入output1.txt文件中.\n"); } voiddijkstra(intC[][n],intv)//求原点v到其余顶点的最短路径及其长度 //C为有向网络的带权邻接矩阵 { intD[n]; intP[n],S[n]; inti,j,k,v1,pre; intmin,max=maxsize,inf=1200; v1=v-1; for(i=0;i { D[i]=C[v1][i];//置初始距离值 if(D[i]! =max) P[i]=v; else P[i]=0; } for(i=0;i S[i]=0;//红点集S开始为空 S[v1]=1;D[v1]=0;//开始点v送S for(i=0;i { min=inf;//令inf>max,保证距离值为max的蓝点能扩充到S中 for(j=0;j { if((! S[j])&&(D[j] { min=D[j]; k=j; } } S[k]=1;//将k+1加入红点集 for(j=0;j { if((! S[j])&&(D[j]>D[k]+C[k][j]))//调整各蓝点的距离值 { D[j]=D[k]+C[k][j];//修改蓝点j+1的距离 P[j]=k+1;//k+1是j+1的前趋 } } }//所有顶点均已扩充到S中 FILE*fp=NULL; fp=fopen("output1.txt","a"); if(fp==NULL) { printf("打开文件失败,程序退出! \n"); } for(i=0;i { fprintf(fp,"%d到%d的最短距离为",v,i+1); fprintf(fp,"%d\n",D[i]);//打印结果 pre=P[i]; fprintf(fp,"路径: %d",i+1); while(pre! =0)//继续找前趋顶点 { fprintf(fp,"<——%d",pre); pre=P[pre-1]; } fprintf(fp,"\n"); } if(fp) { fclose(fp); fp=NULL; } }//dijkstra 用dijkstra方法求得各节点到各点的最短路径长度并输出 用Floyd各点直接的最短距离 #include #defineMAX_VERTEX_NUM36//最大顶点数 #definemaxsize1000//无穷大 typedefintAdjType; typedefstruct{ intpi[MAX_VERTEX_NUM];//存放v到vi的一条最短路径 intend; }PathType; typedefcharVType;//设顶点为字符类型 typedefstruct{ VTypeV[MAX_VERTEX_NUM];//顶点存储空间 AdjTypeA[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 }MGraph;//邻接矩阵表示的图 //Floyd算法 //求网G(用邻接矩阵表示)中任意两点间最短路径 //D[][]是最短路径长度矩阵,path[][]最短路径标志矩阵 voidFloyd(MGraph*G,intpath[][MAX_VERTEX_NUM],intD[][MAX_VERTEX_NUM],intn){ inti,j,k; for(i=1;i<=n;i++){//初始化 for(j=1;j<=n;j++){ if(G->A[i][j] path[i][j]=j; }else{ path[i][j]=-1; } D[i][j]=G->A[i][j]; } } for(k=1;k<=n;k++){//进行n次试探 for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(D[i][j]>D[i][k]+D[k][j]){ D[i][j]=D[i][k]+D[k][j];//取小者 path[i][j]=path[i][k];//改Vi的后继 } } } } } voidmain(){ FILE*fp=NULL; fp=fopen("output3.txt","w"); if(fp==NULL) { printf("打开文件失败\n"); } inti,j,k,v=0,n=6;//v为起点,n为顶点个数 MGraphG; intpath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点的最短路径向量 intD[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点最短路径长度向量 //初始化 AdjTypea[MAX_VERTEX_NUM][MAX_VERTEX_NUM]={ {maxsize,maxsize,15,maxsize,maxsize,maxsize}, {20,maxsize,maxsize,maxsize,10,30}, {maxsize,4,maxsize,maxsize,maxsize,10}, {maxsize,maxsize,maxsize,maxsize,maxsize,maxsize}, {maxsize,maxsize,maxsize,15,maxsize,maxsize}, {maxsize,maxsize,maxsize,4,maxsize,10} }; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ G.A[i][j]=a[i][j]; } } Floyd(&G,path,D,6); for(i=1;i<=n;i++){//输出每对顶点间最短路径长度及最短路径 for(j=1;j<=n;j++){ fprintf(fp,"%d到%d的最短长度: ",i,j); fprintf(fp,"%d\t",D[i][j]);//输出Vi到Vj的最短路径长度 k=path[i][j];//取路径上Vi的后续Vk if(k==-1){ fprintf(fp,"Thereisnopathbetween%d+1and%d+1\n",i,j);//路径不存在 }else{ fprintf(fp,"最短路径为: "); fprintf(fp,"(,%d",i);//输出Vi的序号i while(k! =j){//k不等于路径终点j时 fprintf(fp,",%d",k);//输出k k=path[k][j];//求路径上下一顶点序号 } fprintf(fp,",%d)\n",j);//输出路径终点序号 } fprintf(fp,"\n"); } } if(fp) { fclose(fp); fp=NULL; } printf("文件已写入output3.txt文件中\n"); } 五、实验结果 floyd-output3.txt 七、总结 1、编写本程序时,一开始对读入的数据未进行处理,使得Floyd比较繁琐,后来经改正,在读入时对数据进行处理,使代码简洁了一些。 2、一开始对算法的一些细节没有仔细考略,具体for循环执行多少次就可以完成相应的操作,由于测试数据有限,一开始为发现错误。 后来仔细分析,改掉了错误 THANKS 致力为企业和个人提供合同协议,策划案计划书,学习课件等等 打造全网一站式需求 欢迎您的下载,资料仅供参考
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学