离散数学文档格式.docx
- 文档编号:7558791
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:12
- 大小:110.38KB
离散数学文档格式.docx
《离散数学文档格式.docx》由会员分享,可在线阅读,更多相关《离散数学文档格式.docx(12页珍藏版)》请在冰点文库上搜索。
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;
【打印有向图的邻接矩阵】\n"
for(i=0;
i<
n;
i++)
for(j=0;
j<
j++)
\t%d"
C[i][j]);
【打印原点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;
D[i]=C[v1][i];
//置初始距离值
if(D[i]!
=max)
P[i]=v;
else
P[i]=0;
S[i]=0;
//红点集S开始为空
S[v1]=1;
D[v1]=0;
//开始点v送S
n-1;
i++)//扩充红点集
min=inf;
//令inf>
max,保证距离值为max的蓝点能扩充到S中
j++)//在当前蓝点中选距离值最小的点k+1
if((!
S[j])&
&
(D[j]<
min))
min=D[j];
k=j;
S[k]=1;
//将k+1加入红点集
(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;
a"
%d到%d的最短距离为"
v,i+1);
%d\n"
D[i]);
//打印结果
pre=P[i];
路径:
%d"
i+1);
while(pre!
=0)//继续找前趋顶点
<
——%d"
pre);
pre=P[pre-1];
}//dijkstra
用dijkstra方法求得各节点到各点的最短路径长度并输出
用Floyd各点直接的最短距离
#include<
#defineMAX_VERTEX_NUM36//最大顶点数
#definemaxsize1000//无穷大
typedefintAdjType;
typedefstruct{
intpi[MAX_VERTEX_NUM];
//存放v到vi的一条最短路径
intend;
}PathType;
typedefcharVType;
//设顶点为字符类型
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;
=n;
i++){//初始化
for(j=1;
j++){
if(G->
A[i][j]<
maxsize){
path[i][j]=j;
}else{
path[i][j]=-1;
D[i][j]=G->
A[i][j];
}
for(k=1;
k<
k++){//进行n次试探
i++){
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(){
output3.txt"
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]={
};
G.A[i][j]=a[i][j];
Floyd(&
G,path,D,6);
i++){//输出每对顶点间最短路径长度及最短路径
%d到%d的最短长度:
"
i,j);
%d\t"
D[i][j]);
//输出Vi到Vj的最短路径长度
k=path[i][j];
//取路径上Vi的后续Vk
if(k==-1){
Thereisnopathbetween%d+1and%d+1\n"
//路径不存在
最短路径为:
(,%d"
i);
//输出Vi的序号i
while(k!
=j){//k不等于路径终点j时
%d"
k);
//输出k
k=path[k][j];
//求路径上下一顶点序号
%d)\n"
j);
//输出路径终点序号
if(fp)
{
fclose(fp);
fp=NULL;
}
文件已写入output3.txt文件中\n"
五、实验结果
floyd-output3.txt
七、总结
1、编写本程序时,一开始对读入的数据未进行处理,使得Floyd比较繁琐,后来经改正,在读入时对数据进行处理,使代码简洁了一些。
2、一开始对算法的一些细节没有仔细考略,具体for循环执行多少次就可以完成相应的操作,由于测试数据有限,一开始为发现错误。
后来仔细分析,改掉了错误
THANKS
致力为企业和个人提供合同协议,策划案计划书,学习课件等等
打造全网一站式需求
欢迎您的下载,资料仅供参考
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学
![提示](https://static.bingdoc.com/images/bang_tan.gif)