HUNAN UNIVERSITY
课程实习报告
题目 学生姓名 学生学号 专业年级 指导老师 完成日期
最短路径问题
一、需求分析
本实验是求最短路径的问题，从文件中读入有向网中顶点的数量和顶点间的票价的矩阵，以用户指定的起点，在文件中输出到其余各顶点的最短路径及花费。 （1）输入：
输入的形式：（文件） 5
-1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用户） 输入起点：0
输入值的范围：文件输入中，顶点数和矩阵中顶点间的票价均为整型int，用户输入中，起点数为整型int。 （2）输出的形式： （文件）
源点0到顶点1的最小花费为:5 路径为：0——>2——>1 源点0到顶点2的最小花费为:3 路径为：0——>2
源点0到顶点3的最小花费为:10 路径为：0——>2——>1——>3 源点0到顶点4的最小花费为:18 路径为：0——>2——>4 （3）程序所达到的功能：
在文件中给出有向网的顶点个数和顶点间的票价的矩阵，以用户指定的起点，在文件中输出起点到其余各顶点的最短路径及花费。 （4）测试数据：
a.输入：（文件） 5
-1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用户） 输入起点：0 输出：（文件）
源点0到顶点1的最小花费为:5 路径为：0——>2——>1 源点0到顶点2的最小花费为:3 路径为：0——>2
源点0到顶点3的最小花费为:10 路径为：0——>2——>1——>3 源点0到顶点4的最小花费为:18 路径为：0——>2——>4 b.输入：（文件） 5
-1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用户） 输入起点：2 输出：（文件）
源点2到顶点0：没有连通路径 源点2到顶点1的最小花费为:2
路径为：2——>1
源点2到顶点3的最小花费为:7 路径为：2——>1——>3 源点2到顶点4的最小花费为:15 路径为：2——>4 c.输入：（文件） 6
18 10 3 20 -1 9 15 -1 -1 5 -1 -1 -1 20 16 -1 -1 15 -1 -1 30 -1 6 3 2 9 -1 20 -1 -1 -1 8 12 -1 -1 5 （用户） 输入起点：5 输出：（文件）
源点5到顶点0的最小花费为:21 路径为：5——>1——>3——>4——>0 源点5到顶点1的最小花费为:8 路径为：5——>1
源点5到顶点2的最小花费为:12 路径为：5——>2
源点5到顶点3的最小花费为:13 路径为：5——>1——>3 源点5到顶点4的最小花费为:19 路径为：5——>1——>3——>4 d.输入：（文件） 6
18 10 3 20 -1 9 15 -1 -1 5 -1 -1
-1 20 16 -1 -1 15 -1 -1 30 -1 6 3 2 9 -1 20 -1 -1 -1 8 12 -1 -1 5 （用户） 输入起点：3 输出：（文件）
源点3到顶点0的最小花费为:8 路径为：3——>4——>0 源点3到顶点1的最小花费为:11 路径为：3——>5——>1 源点3到顶点2的最小花费为:11 路径为：3——>4——>0——>2 源点3到顶点4的最小花费为:6 路径为：3——>4
源点3到顶点5的最小花费为:3 路径为：3——>5 e.输入：（文件） 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 （用户） 输入起点：1 输出：（文件）
源点1到顶点0：没有连通路径 源点1到顶点2：没有连通路径 f.输入：（文件） 3 -1 -1 -1
-1 -1 -1 -1 -1 -1 （用户） 输入起点：3 输出：（文件）
源点3到顶点0的最小花费为:-572562307 路径为：3——>1——>0
源点3到顶点1的最小花费为:-572662307 路径为：3——>1
源点3到顶点2的最小花费为:-572662307 路径为：3——>2 二、概要设计
（1）所有抽象数据类型的定义： const int MaxNum=100000; //利用邻接矩阵存储图： class Graph { private:
int *Adj;//保存邻接矩阵的一维数组j和k之间权值存储在Adj[j*Num+k]中 int Num;
public: };
（2）算法的基本思想：
采用邻接矩阵为图的存储结构，保存邻接矩阵的一维数组j和k之间权值存储Adj[j*Num+k]中，以用户指定的起点，进行弗洛伊德算法，先初始化最短路径，对角线元素设置为0，其
Graph(); ~Graph();
void Floyd(int start);
他元素设置为边的权值，没有有向边设置为MaxNum，依次插入中间点k，判断是否检查Dis(i,k) + Dis(k,j)
（3）主程序的流程以及各程序 程序由三个模块组成：
输入模块：读取文件中的顶点个数及各边权值，将图存储在邻接矩阵中，在用户界面输入起点数。
功能模块：利用Floyd算法，初始化最短路径，依次插入中间点判断是否路径更短，更新至最短路径，循环结束，路径入栈。
输出模块：在文件中输出打印起点到其余各点的最短路径。
（4）模块之间的层次关系 输入模块->功能模块->输出模块 三、详细设计
（1）实现概要设计中定义的所有数据类型：
利用邻接矩阵存储图，边间权值存储在一维数组存储Adj[j*Num+k]中，顶点数和权值均为整型int；最大值、起点数、最短权值、路径、顶点域均为整型int。 //利用邻接矩阵存储图： class Graph { private:
int *Adj;//保存邻接矩阵的一维数组j和k之间权值存储在Adj[j*Num+k]中 int Num;
public:
Graph(); ~Graph();
void Floyd(int start);
};
const int MaxNum=100000;
int*dist=new int[Num];
（2）算法的具体步骤:
1>.读取文件中的顶点个数及各边权值；
2>.利用邻接矩阵存储图，用户输入起点数，进行Floyd算法；
3>.初始化最短路径，对角线元素设置为0，其他元素设置为边的权值，没有有向边设置为MaxNum；
4>.依次插入中间点k，判断是否检查Dis(i,k) + Dis(k,j) .若不成立，则路径不改变；
6>.若成立，则更新最短路径，设置Dis(i,j) = Dis(i,k) + Dis(k,j)； 7>.递归访问直至所有中间点均被访问，则循环结束，路径入栈； 8>.在文件中输出打印最短路径及花费。 流程图：
int*prev=new int[Num]; int*s=new int[Num];
注：由于VISIO无法正常运行，流程图无法用此软件绘制。
（3）算法的时空分析：
Floyd算法的时间复杂度为O（n³）。 四、调试分析
仅输出最小花费，而无法输出最短路径：
解决方法：
初始化一个栈，将路径存入栈中，之后pop操作弹出路径即可。
五、测试结果 a.案例输入： 输入：（文件） 5
-1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用户） 输入起点：0 输出：（文件）
源点0到顶点1的最小花费为:5 路径为：0——>2——>1 源点0到顶点2的最小花费为:3 路径为：0——>2
源点0到顶点3的最小花费为:10 路径为：0——>2——>1——>3 源点0到顶点4的最小花费为:18 路径为：0——>2——>4
b.输入：（文件） 5
-1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用户） 输入起点：2 输出：（文件）
源点2到顶点0：没有连通路径 源点2到顶点1的最小花费为:2
路径为：2——>1
源点2到顶点3的最小花费为:7 路径为：2——>1——>3 源点2到顶点4的最小花费为:15 路径为：2——
>4
c.输入：（文件） 6
18 10 3 20 -1 9 15 -1 -1 5 -1 -1 -1 20 16 -1 -1 15 -1 -1 30 -1 6 3 2 9 -1 20 -1 -1
-1 8 12 -1 -1 5 （用户） 输入起点：5 输出：（文件）
源点5到顶点0的最小花费为:21 路径为：5——>1——>3——>4——>0 源点5到顶点1的最小花费为:8 路径为：5——>1
源点5到顶点2的最小花费为:12 路径为：5——>2
源点5到顶点3的最小花费为:13 路径为：5——>1——>3 源点5到顶点4的最小花费为:19 路径为：5——>1——>3——
>4
d.输入：（文件） 6
18 10 3 20 -1 9 15 -1 -1 5 -1 -1 -1 20 16 -1 -1 15 -1 -1 30 -1 6 3 2 9 -1 20 -1 -1 -1 8 12 -1 -1 5 （用户） 输入起点：3 输出：（文件）
源点3到顶点0的最小花费为:8 路径为：3——>4——>0 源点3到顶点1的最小花费为:11 路径为：3——>5——>1 源点3到顶点2的最小花费为:11 路径为：3——>4——>0——>2 源点3到顶点4的最小花费为:6 路径为：3——>4
源点3到顶点5的最小花费为:3
路径为：3——
>5
e.输入：（文件） 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 （用户） 输入起点：1 输出：（文件）
源点1到顶点0：没有连通路径
源点1到顶点2：没有连通路径
f.输入：（文件） 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 （用户） 输入起点：3 输出：（文件）
源点3到顶点0的最小花费为:-572562307 路径为：3——>1——>0
源点3到顶点1的最小花费为:-572662307 路径为：3——>1
源点3到顶点2的最小花费为:-572662307 路径为：3——>2
六、用户使用说明
1.本程序运行环境为Win7 64位操作系统下VC6.0，执行文件为最短路径问题.exe. 2.要求首先在文件中输入顶点数及各边的票价矩阵，再在用户界面输入起点数。 输入范例：
输入：（文件） 5
-1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 （用户）
输入起点：0 输出：（文件）
源点0到顶点1的最小花费为:5 路径为：0——>2——>1 源点0到顶点2的最小花费为:3 路径为：0——>2
源点0到顶点3的最小花费为:10 路径为：0——>2——>1——>3 源点0到顶点4的最小花费为:18 路径为：0——>2——>4 七、实验心得
本次实验要求读取文件中的顶点数及各边权值，输入起点数，在文件中输出起点到其余各点的最短路径及花费，由于涉及全局任意两点最短路径，因此我采用Floyd算法，通过初始化路径，不断插入中间点进行比较路径长短，更新最短路径直至循环结束，输出最短路径及花费。Floyd算法较Dijkstra算法容易实现，但时间复杂度大，适合任意两点间的最短路径问题，如果确定起点终点则采用Dijkstra算法。 八、源程序
#include #include #include using namespace std; const int MaxNum=100000; class Graph { private:
int *Adj;//保存j和k之间权值存储在一位数组Adj[j*Num+k]中 int Num;
public:
~Graph();
void Floyd(int start); };
/*构造函数*/ Graph::Graph() { }
/*析构函数*/ Graph::~Graph() {
ifstream input("input.txt",ios::in); if(input==NULL)
cout
if(input!=NULL) { }
input>>Num;
Adj=new int[Num*Num]; if(Adj==NULL)
exit(0);
for(int i=0;i
for(int j=0;j
input>>Adj[i*Num+j]; if(Adj[i*Num+j]==-1)
Adj[i*Num+j]=MaxNum;
}
/*弗洛伊德算法*/
void Graph::Floyd(int start) {
int*dist=new int[Num];//最短权值 int*prev=new int[Num];//路径
int*s=new int[Num];//s为已经访问的顶点域 int i,j,k,m; m=start;
for(i=0;i
//初始化
{ }
prev[m]=-1; s[m]=1;
for(i=0;i
dist[i]=Adj[m*Num+i]; prev[i]=m; s[i]=0;
//Num-1次递归
{
int min;
for(k=0;k
min=dist[k]; j=k;
if(!s[k]) break;
if(!s[k]&&dist[k]
//更新最短路径
} ofstream output("output.txt",ios::out); if(output==NULL) exit(0); if(!s[k]&&dist[j]+Adj[j*Num+k]=MaxNum) { output
} else { output
j=k;
- 21 -
output";Q.pop();} output
}
}
int main()
{
Graph G;
cout
int start;
cin>>start;
G.Floyd(start);
getchar();
return 0;
}
- 22 -