离散数学.doc

离散数学——最小路径问题及其编程求解
一、 实验目的
通过本次实验的学习，理解最小路径问题及其编程求解.
二、 实验内容
用C语言编程实现求赋权图中任意两点间最短路径的Floyd算法，并能对给定的两结点自动求出最短路径。
三、 使用环境
设备：PC机
操作系统：Windows
编译软件：visual C++ 6.0
四、源代码及调试过程
节点1到其余个点的最短路径长度,并输出
#include<stdio.h>
#define maxsize 1000 //表示两点间不可达，距离为无穷远
#define n 6 //结点的数目
void dijkstra(int C[][n],int v);//求原点v到其余顶点的最短路径及其长度
void main()
{
FILE*fp=NULL;
fp=fopen("output1.txt","w");
if(fp==NULL)
{
printf("打开文件失败，程序退出！\n");
}

fprintf(fp," ——Dijkstra算法——\n");
int C[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");
}
void dijkstra(int C[][n],int v)//求原点v到其余顶点的最短路径及其长度
//C为有向网络的带权邻接矩阵
{
int D[n];
int P[n],S[n];
int i,j,k,v1,pre;
int min,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;
else
P[i]=0;
}
for(i=0;i<n;i++)
S[i]=0; //红点集S开始为空
S[v1]=1;D[v1]=0; //开始点v送S
for(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>
#define MAX_VERTEX_NUM 36 //最大顶点数
#define maxsize 1000 //无穷大

typedef int AdjType;

typedef struct{
int pi[MAX_VERTEX_NUM];//存放v到vi的一条最短路径
int end;
}PathType;

typedef char VType; //设顶点为字符类型

typedef struct{
VType V[MAX_VERTEX_NUM]; //顶点存储空间
AdjType A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
}MGraph;//邻接矩阵表示的图

//Floyd算法
//求网G（用邻接矩阵表示）中任意两点间最短路径
//D[][]是最短路径长度矩阵，path[][]最短路径标志矩阵
void Floyd(MGraph * G,int path[][MAX_VERTEX_NUM],int D[][MAX_VERTEX_NUM],int n){
int i,j,k;
for(i=1;i<=n;i++){//初始化
for(j=1;j<=n;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<=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的后继
}
}
}
}
}

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 path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点的最短路径向量
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点最短路径长度向量

//初始化
AdjType a[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,"There is no path between %d+1 and %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循环执行多少次就可以完成相应的操作，由于测试数据有限，一开始为发现错误。后来仔细分析，改掉了错误