最短路径_数据结构课程设计报告_数据结构课程设计报告
最短路径_数据结构课程设计报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计报告”。
数据结构课程设计
《数据结构》课程设计报告
设计题目：____医院选址____________ 姓名：__________________ 学号：________________ 专业：___________
院系：____________
班级：_________________ 指导教师：_________________
年 1月 3 日
数据结构课程设计
一、问题描述
(1)题目内容：有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总和来说较短。（n>=5）(2)基本要求：
(3)可以输出每一对点间的路径长度；然后选取偏心度，最小的偏心度即为所求。
二、需求分析
(4)本程序的功能包括找出每一对点间的路径长度。(5)然后算出每一对点的偏心度。(6)其中最小的偏心度即为所求。
三、概要设计
操作集合：
(7)public:MGraph(DataType a[],int b[][MaxSize],int n,int e);//初始化邻接矩阵和路径
(8)void Floyd();//弗洛伊德算法的实现(9)void getE();//获取偏心度
(10)void showdist();//把每一对顶点之间的路径权值show出来(11)~MGraph(){} //类的析构函数
四、数据结构设计
(1)DataType vertex[MaxSize];//存放图中顶点的数组(2)int
arc[MaxSize][MaxSize];//存放图中边的数组
(3)string path[MaxSize][MaxSize];//存放从Vi到Vj的最短路径，初始为
//path[i][j]=“ViVj”
(4)int dist[MaxSize][MaxSize];//存放求得的最短路径长度(5)int vertexNum, arcNum;//图的顶点数和边数(6)int E[MaxSize][2];//获取最小偏心度和该顶点
五、算法设计
1.算法分析
1）对带权有向图的，调用Floyd算法，对每一对顶点间的最短路径长度的矩阵；
2）对最短路径长度矩阵的每列求最大值，即得到各点的偏心度； 3)具有最小偏心度的顶点即为所求。
数据结构课程设计
数据结构课程设计
2.算法实现
#include #include #include using namespace std;
const int MaxSize = 5;template cla MGraph { public:，建立具有n个顶点e条边的图
};template MGraph::MGraph(DataType a[], int b[][MaxSize],int n,int e){
} template void MGraph::Floyd(){ int i,j,k;
MGraph(DataType a[], int b[][MaxSize],int n,int e);//构造函数
void Floyd();void getE();void showdist();~MGraph(){} DataType vertex[MaxSize];int arc[MaxSize][MaxSize];int dist[MaxSize][MaxSize];int vertexNum, arcNum;int E[MaxSize][2];
//存放图中顶点的数组 //存放图中边的数组 //存放求得的最短路径长度 //图的顶点数和边数 private:
string path[MaxSize][MaxSize];//存放从Vi到Vj的最短路径，初始为path[i][j]=“ViVj” vertexNum = n;arcNum = e;for(int i=0;i
} arc[i][j]=b[i][j];dist[i][j]=arc[i][j];
//直接放入邻接矩阵
for(int j=0;j
数据结构课程设计
} for(i=0;i
} for(k=0;k
for(i=0;i
}
//顶点i和j之间是否经过顶点k for(j=0;j
} dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=path[i][k]+path[k][j];for(j=0;j
} dist[i][j]=arc[i][j];if(dist[i][j]!=10000)else path[i][j]=“”;path[i][j]=vertex[i]+vertex[j];
template void MGraph::showdist(){
} template void MGraph::getE(){
心度。
} for(int i=0;i
}
for(int i=0;i
} for(int j=0;j
“;for(int i=0;i
E[i][0]=i;//存放某一个节点的序号 E[i][1]=0;//存放节点的最短路径，权值。
int max = dist[0][i];//i表示列；j表示行。for(int j=0;j
if(dist[j][i]>max){ } E[i][1]=max;max = dist[j][i];
数据结构课程设计
cout
} void main(){
代表是无穷。
}
MGraph GM(a,b,5,7);GM.Floyd();GM.showdist();cout
0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};char a[5] = {'A','B','C','D','E'};int b[5][5] = {
//邻接矩阵,A,B,C,D,E是节点的信息，代表某一个地点。
//存储某两个有向节点间的权值，代表路径长度，10000 int min=E[0][1],k;for(int i=0;i
} cout
cout
if(E[i][1]
} min=E[i][1];k=i;
六、程序测试与实现
1、函数之间的调用关系
Main
Floyd()
showdist()
getE()
2、主程序
void main(){ char a[5] = {'A','B','C','D','E'};
//邻接矩阵,A,B...是节点的信息，代表某一个地点。
数据结构课程设计
int b[5][5] = { //存储某两个有向节点间的权值，代表路径长度，10000代表是无穷。
0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};
MGraph GM(a,b,5,7);
}
GM.Floyd();
GM.showdist();
cout
GM.getE();
3、测试数据
int b[5][5] = { //存储某两个有向节点间的权值，代表路径长度，10000代表是无穷。
0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};
4、测试结果
七、调试分析
数据结构课程设计
1．在算偏心度的时候；每一列的最大值算错了，下次要注意。
在show的时候也把行和列搞反了；所以以为结果不对其是对的。2．算法的时空分析：(1)时间复杂度:O(n^3)；(2)空间复杂度:O(n^2)[1]
八、遇到的问题及解决办法
1）在算偏心度的时候；每一列的最大值算错了，下次要注意。
解决办法：是把行变，列不变。
2)在show的时候也把行和列搞反了；所以以为结果不对其是对的。
解决办法：把行和列反一下就好。
九、心得体会
Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX)+ Dis(XB)
