离散数学.doc

离散数学——最小路径问题及其编程求解实验目的通过本次实验的学习，理解最小路径问题及其编程求解.实验内容用C语言编程实现求赋权图中任意两点间最短路径的Floyd算法，并能对给定的两结点自动求出最短路径。使用环境设备：PC机操作系统：Windows编译软件：visualC++6.0四、源代码及调试过程节点1到其余个点的最短路径长度,并输出#include<stdio.h>#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<n;i++){for(j=0;j<n;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<n;i++){D[i]=C[v1][i];//置初始距离值if(D[i]!=max)P[i]=v;elseP[i]=0;}for(i=0;i<n;i++)S[i]=0;//红点集S开始为空S[v1]=1;D[v1]=0;//开始点v送Sfor(i=0;i<n-1;i++)//扩充红点集{min=inf;//令inf>max，保证距离值为max的蓝点能扩充到S中for(j=0;j<n;j++)//在当前蓝点中选距离值最小的点k+1{if((!S[j])&&(D[j]<min)){min=D[j];k=j;}}S[k]=1;//将k+1加入红点集for(j=0;j<n;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<n;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<stdio.h>#defineMAX_VERTEX_NUM36//最大顶点数#definemaxsize1000//无穷大typedefintAdjType;typedefstruct{intpi[MAX_VERTEX_NUM];//存放v到vi的一条最短路径intend;}PathType;typedefcharVType;//设顶点为字符类型typedefstruct