离散数学——最小路径问题及其编程求解.doc

离散数学最小路径问题及其编程求解1、 实验目的 通过本次实验的学习，理解最小路径问题及其编程求解.2、 实验内容用C语言编程实现求赋权图中任意两点间最短路径的Floyd算法，并能对给定的两结点自动求出最短路径。3、 使用环境设备：PC机操作系统：Windows编译软件：visual C+ 6.0四、源代码及调试过程节点1到其余个点的最短路径长度,并输出#include#define maxsize 1000 /表示两点间不可达，距离为无穷远#define n 6 /结点的数目void dijkstra(int Cn,int v);/求原点v到其余顶点的最短路径及其长度void main()FILE*fp=NULL;fp=fopen(output1.txt,w);if(fp=NULL)printf(打开文件失败，程序退出！n); fprintf(fp, Dijkstra算法n); int Cnn= 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;in;i+) for(j=0;jn;j+) fprintf(fp,t%d,Cij); fprintf(fp,n); fprintf(fp,【打印原点1到其他各点的最短路径及其长度】n); if(fp)fclose(fp);fp=NULL; dijkstra(C,v); printf(文件已写入output1.txt文件中.n);void dijkstra(int Cn,int v)/求原点v到其余顶点的最短路径及其长度/C为有向网络的带权邻接矩阵 int Dn; int Pn,Sn; int i,j,k,v1,pre; int min,max=maxsize,inf=1200; v1=v-1; for(i=0;in;i+) Di=Cv1i; /置初始距离值 if(Di!=max) Pi=v; else Pi=0; for(i=0;in;i+) Si=0; /红点集S开始为空 Sv1=1;Dv1=0; /开始点v送S for(i=0;imax，保证距离值为max的蓝点能扩充到S中 for(j=0;jn;j+)/在当前蓝点中选距离值最小的点k+1 if(!Sj)&(Djmin) min=Dj; k=j; Sk=1; /将k+1加入红点集 for(j=0;jDk+Ckj)/调整各蓝点的距离值 Dj=Dk+Ckj; /修改蓝点j+1的距离 Pj=k+1; /k+1是j+1的前趋 /所有顶点均已扩充到S中 FILE*fp=NULL;fp=fopen(output1.txt,a);if(fp=NULL)printf(打开文件失败，程序退出！n); for(i=0;in;i+) fprintf(fp,%d到%d的最短距离为,v,i+1); fprintf(fp,%dn,Di); /打印结果 pre=Pi; fprintf(fp,路径：%d,i+1); while(pre!=0) /继续找前趋顶点 fprintf(fp,%d,pre); pre=Ppre-1; fprintf(fp,n); if(fp)fclose(fp);fp=NULL; /dijkstra用dijkstra方法求得各节点到各点的最短路径长度并输出用Floyd各点直接的最短距离#include #define MAX_VERTEX_NUM 36 /最大顶点数#define maxsize 1000 /无穷大 typedef int AdjType; typedef struct int piMAX_VERTEX_NUM;/存放v到vi的一条最短路径 int end;PathType; typedef char VType; /设顶点为字符类型typedef struct VType VMAX_VERTEX_NUM; /顶点存储空间 AdjType AMAX_VERTEX_NUMMAX_VERTEX_NUM; /邻接矩阵 MGraph;/邻接矩阵表示的图/Floyd算法/求网G（用邻接矩阵表示）中任意两点间最短路径 /D是最短路径长度矩阵，path最短路径标志矩阵 void Floyd(MGraph * G,int pathMAX_VERTEX_NUM,int DMAX_VERTEX_NUM,int n) int i,j,k; for(i=1;i=n;i+)/初始化 for(j=1;jAijAij; for(k=1;k=n;k+)/进行n次试探 for(i=1;i=n;i+) for(j=1;jDik+Dkj) Dij=Dik+Dkj;/取小者 pathij=pathik;/改Vi的后继 void main()FILE*fp=NULL;fp=fopen(output3.txt,w);if(fp=NULL)printf(打开文件失败 n); int i,j,k,v=0,n=6;/v为起点，n为顶点个数 MGraph G; int pathMAX_VERTEX_NUMMAX_VERTEX_NUM;/v到各顶点的最短路径向量 int DMAX_VERTEX_NUMMAX_VERTEX_NUM;/v到各顶点最短路径长度向量 /初始化 AdjType aMAX_VERTEX_NUMMAX_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.Aij=aij; 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,%dt,Dij);/输出Vi到Vj的最短路径长度 k=pathij;/取路径上Vi的后续Vk if(k=-1) fprintf(fp,There is no path between %d+1 and %d+1n,i,j);/路径不存在 else fprintf(fp,最短路径为:); fprintf(fp,(,%d,i);/输出Vi的序号i while(k!=j)/k不等于路径终点j时 fprintf(fp,%d,k);/输出k k=pathkj;/求路径上下一顶点序号 fprintf(fp,%d)n,j);/输出路径终点序号 fprintf(fp,n); if(fp)fclose(fp);fp=NULL;printf(文件已写入output3.txt文件