数据结构实验报告十一—最短路径问题

问题描述：

若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。

基本要求：

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

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

一、需求分析：

1、本程序需要用矩阵来存储图的各种信息。

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

终点 4

输出

18

实现提示：

（1）设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。

（2）此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。

（3） Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。

（4）考虑没有路径时的输出。

二、概要设计：

抽象数据类型：

为实现上述功能需建立一个二维数组和图类。

算法的基本思想：

1、图的信息的读取：

定义一个二维数组，将图的信息读入，并将两边距离为-1的

边转换为一个较大的数（>>途中各点之间的距离）。

2、Dijkstra算法：

根据输入的第一个结点首先找到（直接距离）该点最近的A，

则这两点之间的边是必须的，然后比较通过A到其他点的距离l1和直接到其他点的距离l2。如果l1

程序的流程

程序由三个模块组成：

输入模块：读入图的信息（用矩阵进行存储）。

处理模块：Dijkstra算法。

输出模块：将收入结点到其他点的最短距离输出。

三、详细设计

算法的具体步骤：

#define N 30

int a[N][N];

class Graph{

private:

int ver;

public:

Graph(int v){ver=v;}

void build();

void Dijkstra(int start,int end);

void printf(int start);

};

void Graph::build(){ //构建图

int temp,max=1000;

for(int i=0;i

for(int j=0;j

cin>>temp;

if(temp==-1)

//-1表示两点之间无直接联系，将距离赋为500

a[i][j]=1000;

else

a[i][j]=temp;

}

}

void Graph::Dijkstra(int start,int end){ //最小路径的算法 int dist[N],s[N];

int i,j,min,pos;

for(i=0;i

if(i==start)

s[i]=1; //标记边是否被访问

else

s[i]=0;

}

for(i=0;i

dist[i]=a[start][i]; //该点到其他边的距离

for(i=0;i

for(j=0;j

if(s[j]==0 && dist[j]

min=dist[j];

//找出最小边,则该边是最短路径所必须的

pos=j;

}

}

s[pos]=1;

for(j=0;j

if(dist[j]>dist[pos]+a[pos][j])

//如过通过pos这条边的距离小于原先的距离

dist[j]=dist[pos]+a[pos][j]; //改变距离

}

}

for(i=0;i

if(i!=start) //不会有起点到起点的路径

cout<"<

}

}

int main(){

int v,start,end;

cin>>v;

Graph G(v);

G.build();

cin>>start>>end;

G.Dijkstra(start,v-1);

system("pause");

return 0;

}

四、调试分析

略。

五、测试结果

本实验的测试结果截图如下：

注：此处由于不会用文件流输入和输出，故在命令提示符上直接进行输入。

六、用户使用说明（可选）

1 、本程序的运行环境为windows 操作系统，执行文件为zuiduanlu.exe

2 、运行程序时

提示输入数据并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果。

七、实验心得（可选）

1、编写本程序时，一开始对读入的数据未进行处理，使得Dijkstra比较繁琐，后来经改正，在读入时对数据进行处理，使代码简洁了一些。

2、一开始对算法的一些细节没有仔细考略，具体for循环执行多少次就可以完成相应的操作，由于测试数据有限，一开始为发现错误。后来仔细分析，改掉了错误。

附录（实验代码）：

#include

using namespace std;