实验11 最短路径问题实验报告

通信2班 谢宗欣20100820219 叶恒 20100820220 张琼 20100820221 背景

乘汽车旅行的人总希望找出到目的地的尽可能短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？ 计算机网络中的路由就是通过互联的网络把信息从源地址传输到目的地址的活动。为了高效引导数据的传输，如何找出源和目的地址之间的最优路径？

这些问题中的网络（交通网，计算机通信网）可以使用一个带权图来建模，寻找最优路的需求可转换为带权图的最短路径问题。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和边组成的）中两结点之间的最短路径。 问题具体的形式包括：

 确定起点的最短路径问题，即已知起始结点，求最短路径的问题。适合使用Dijkstra

算法。

 确定终点的最短路径问题，与确定起点的问题相反，该问题是已知终结结点，求最

短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

 确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径。  全局最短路径问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。

问题描述

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

基本要求

（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） 考虑没有路径时的输出。

抽象数据类型

用二维数组实现邻接矩阵

主要函数

Mark getMark(Docu*D , int i)

void setMark(Docu*D,int v,Mark m) int first(Docu*D , int v)

int next(Docu*D , int v , int w) int weight(Docu*D,int v,int w) int minVertex(Docu*D , int *B) void Dijkstra(Docu*D , int *B , int s)

算法实现

#include #include #include #include using namespace std;

enum Mark {UNVISITED,VISITED};

typedef struct DocuNode {

int n; Mark m; } DocuNode;

typedef struct Docu {

int n;

DocuNode * Node; int** edge; } Docu;

Mark getMark(Docu*D , int i) {

return D->Node[i].m; }

void setMark(Docu*D,int v,Mark m) {

D->Node[v].m=m; }

int first(Docu*D , int v) {

int i;

for(i=0 ; in ; i++)

if((D->edge[v][i])!=-1) return i; return i; }

int next(Docu*D , int v , int w) {

int i;

for(i=w+1 ; in ; i++) if((D->edge[v][i])!=-1) return i; return i; }

int weight(Docu*D,int v,int w) {

return D->edge[v][w]; }

int minVertex(Docu*D , int *B) {

int i , v;

for(i=0; in; i++)

if(getMark(D,i)==UNVISITED) {

v=i; break; }

for(i++; in; i++)

if(getMark(D,i)==UNVISITED&&((((B[i]return v; }

void Dijkstra(Docu*D , int *B , int s) {

int i,v,w;

for(i=0; in; i++) {

v=minVertex(D,B); if(B[v]==-1) return; setMark(D,v,VISITED);

for(w=first(D,v); wn; w=next(D,v,w))

if((B[w]>(B[v]+weight(D,v,w)))||(B[w]==-1)) B[w]=B[v]+weight(D,v,w); } }

int main() {

Docu* D;

ifstream fin(\"Docu.txt\"); int i , j;

D=(Docu*)malloc(sizeof(Docu)); fin>>D->n;//从文件中读取节点数

D->Node=(DocuNode*)malloc(sizeof(DocuNode)); for(i=0 ; in ; i++)

D->Node[i].m=UNVISITED; //将所有节点设为未被访问的

D->edge=(int**)calloc(1,sizeof(int*)*D->n); if(!D->edge) //若内存未分配成功 cout<<\"error\"; for(i=0 ; in ; i++) {

D->edge[i]=(int*)calloc(1,sizeof(int)*D->n); if(!D->edge[i]) //若内存未分配成功 cout<<\"error\"; }

for(i=0 ; in ; i++) for(j=0 ; jn ; j++)

fin>>D->edge[i][j]; //从文件中读取边权值

int start , end;

cout<<\"起点:\"<>start;

cout<<\"终点:\"<>end;

int *B;

B=(int *)malloc(D->n*sizeof(int));

for(i=0 ; in ; i++)

B[i]=D->edge[start][i];

Dijkstra(D,B,start);

cout<叶恒

心得：本次实验运用书本代码顺利地完成。过程中加深了对最短路劲Dijkstra算法的理解与运用，熟悉了图的邻接矩阵表示法，同时学会了文件调用方面的方法，能力有一定提升。 谢宗欣

感觉数据结构越来越吃力了，这学期实验好多了，每一个都不好对付，到现在我只能说我会尽力而为了。 张琼

这次实验主要是对书中的代码进行改写和添加。其中对文件的读取和运用让我又有了新的掌握这次实验不难，但是也需要认真才能完成。