最短路径实验报告

HUNAN UNIVERSITY

课程实习报告

题 目： 最短路径问题 学生姓名 学生学号 20110801328 专业班级 计算机科学与技术（3）班 完 成 日 期 2013.5.29

一、 需 求 分 析：

1.若用有向网表示某地区的公路交通网，其中顶点表示该地区的

一些主要场所，弧表示已有的公交线路，弧上的权表示票价。试设计

一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达

另一场所。

2.本程序要求：

（1）从文件中读取有限网中顶点的数量和顶点间票价的矩阵。

（2）以用户指定的起点和终点，输出从起点到终点的花费。

3.在dos系统下输入起点，并输出最短路径。

4.测试数据：

输入

（文件）

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

终点 4

输出

18

二、 概要设计

为实现上述功能需要用到图的存储结构。

利用邻接矩阵构造图，并求出某一顶点到另一顶点的最短路径并

打印输出。

三、 算法基本思想

根据题目要求用弗洛伊德算法可以实现两点最短路径问题。弗洛

伊德算法仍然使用图的邻接矩阵arcs[n+1][n+1]来存储带权有向图。

算法的基本思想是:设置一个n x n的矩阵A(k)，其中除对角线的元素

都等于0外，其它元素a(k)[i][j]表示顶点i到顶点j的路径长度，K

表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路

径长度，没有有向边时，路径长度为∞，当K=0时, A (0)[i][j]=arcs[i][j]，

以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间

顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原

路径，修改矩阵元素。

四、 程序设计流程

程序由三个模块组成：

1.输入模块：起点终点和各点间的权值这都从文件中读取。

2.求最短路径模块：通过弗洛伊德算法求出起点终点最短路径。

3.输出模块：完成弗洛伊德算法后，把最短路径给出，并给出具

体路径。

五、 程序源代码

#include<iostream>

#include<stack>

#include<fstream>

using namespace std;

const int MaxNum=100000;

class Graph

{

private:

int *Adj; //保存邻接矩阵的一维数组 j和k之间权值 存储在

Adj[j*Num+k]中

int Num;//当前顶点数

public:

Graph(); //构造函数

~Graph();//析沟函数

void Dijkstra(int start);//单元最短路径算法

};

Graph::Graph() //构造函数

{

ifstream input("input.txt",ios::in);

if(input==NULL)cout<<"open error!\n";

if(input!=NULL)

{

input>>Num;

Adj=new int[Num*Num];

if(Adj==NULL)exit(0);

for(int i=0;i<Num;i++)

for(int j=0;j<Num;j++)

{

input>>Adj[i*Num+j];

if(Adj[i*Num+j]==-1)

Adj[i*Num+j]=MaxNum;

}

}

}

Graph::~Graph()//析构函数

{

delete []Adj;

}

void Graph::Dijkstra(int start)//单元最短路径算法

{

int*dist=new int[Num];//记录最短权值

int*prev=new int[Num]; //记录路径

int*s=new int[Num];//s为已经确定好的顶点域

int i,j,k,m; //j记录dist的下标

m=start;

for(i=0;i<Num;i++) //初始化

{

dist[i]=Adj[m*Num+i];

prev[i]=m; //记录源点到顶点的最短路径上，本顶点的前一顶点

s[i]=0; //顶点i不在s域中

}

prev[m]=-1; //m是源点 前一顶点不存在

s[m]=1;//源点在s域中

for(i=0;i<Num-1;i++) //差Num-1个顶点需处理

{

int min; //最小权

for(k=0;k<Num;k++) if(!s[k])break; //找到仍在顶点V-S域中的第一个顶点

min=dist[k];

j=k;

for(k=j+1;k<Num;k++) //找最小权值的边

if(!s[k]&&dist[k]<min)

{

min=dist[k];

j=k;

}

s[j]=1; //放进s域中

for(k=0;k<Num;k++) //更新最短路径值

if(!s[k]&&dist[j]+Adj[j*Num+k]<dist[k])

{

dist[k]=dist[j]+Adj[j*Num+k]; //记录最短路径

prev[k]=j; //记录路径 即本顶点k的前驱顶点j }

}

ofstream output("output.txt",ios::out);

if(output==NULL)exit(0);

for(k=0;k<Num;k++) //输出打印

if(k!=m)

{

if(dist[k]>=MaxNum)

{

output<<"源点"<<start<<"到顶点"<<k<<"不存在相通的路径"<<endl<<endl;

}

else

{

output<<"源点"<<start<<"到顶点"<<k<<"的最小花费为:"<<dist[k]<<endl; //输

出最小权值

j=k;

stack<int>Q;

output<<"路径为：";

while(j!=m){Q.push(j);j=prev[j];} //路径存入栈中

Q.push(j);

while(Q.size()!=1){output<<Q.top()<<"-->";Q.pop();} //输出路径

output<<Q.top()<<endl<<endl;Q.pop(); //最后一个元素出栈

}

}

}

int main()

{

Graph G;

cout<<"请输入起点："<<endl;

int start;

cin>>start;

G.Dijkstra(start);

getchar();

getchar();

return 0;

}

六、 程序输入输出结果

七、 实验心得

这个实验比较难，尤其在求在众多路径中找到那条最短路径。不光要考虑与其相邻下一顶点的最短路径，还要考虑到起到最终要到大的点的所有路径的最小值。 最后解决方法是先找出最小权值的边，然后遍历其他边。再用上一条加上所遍历的边。以求的最短路径。如图：

1到3的最短边是8，但是这不是1到3的最短路径，就要

用1到2，2到3的路径长度相加代替1到3的最短路径。

本文来源：https://www.bwwdw.com/article/wb61.html