数据结构程序设计

《数据结构》课程设计

题目：确定任两个交通站点间最短路径的算法及实现姓名：

学院：信息工程学院

专业：12级计科

班级：物联网工程

学号：

指导教师：叶茂功

2014年6月10日

确定任两个交通站点间最短路径的算法及实现

摘要：在纷繁复杂的城市公交网中，如果想寻找到一条从当前某个站点到达另一个目的站点的最短路径，应该怎样实现呢？针对这个问题，采用数据结构中最短路径的思想进行了思考和研究，并采用(Floyd)算法来实现搜寻计算操作和过程.

目录

一课题分析 (4)

设计要求 (4)

一、目的 (4)

二、实验内容 (4)

三、数据结构及算法思想 (4)

四、弗洛伊德（Floyd)算法流程 (5)

五、基本需求 (5)

六、程序设计 .................................................................. 错误！未定义书签。

七、运行及调试结果 (9)

八、总结 (10)

参考文献 (10)

设计要求

一、目的

1、掌握图的基本存储方法；

2、掌握有关图的操作算法并用高级语言实现；

3、熟练掌握图的两种搜索路径的遍历方法。

二、实验内容

假设以一个带权有向图表示某一区域的公交线路网，图中5个顶点代表区域中的重要交通站点，弧代表已有的公交线路，弧上的权表示该线路上的距离（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最短的距离（或最少的时间）从区域中的某一交通站点到达另一交通站点。

三、数据结构及算法思想

用Floyd求每对顶点之间最短路径算法解决，矩阵A用来进行n 次迭代的数值，矩阵P用来记录路径，P[i][j]为迭代过程中当前已经求得的从顶点i到顶点j的最短路径上最后被插入的那个顶点。

四、弗洛伊德（Floyd ）算法流程

五、基本需求

1.建立交通网络图的存储结构；

2.单元最短路径问题；

3．实现两个交通站点间的最短路径问题

开始

初始化距离和路径

设Di,j,k 为从i 到j 的只以（1…k ）集合中的节点为中间节点的最短路径的长度

Di,j,k=Di,k,k-1+Dk,j,k-1

Di,j,k=min(Di,k,k-1+Dk,j,k-1,Di,j,k-1)

Di,j,k=Di,j,k-1

最

短路径不过 点 k

最短路径过点k

六、程序设计

#define m 9

#define MaxNum 999 /*定义一个最大数*/

#include

/* 定义邻接矩阵类型*/

typedef int adjmatrix[m][m];

/* 建立图的邻接矩阵*/

void CreatMatrix(adjmatrix G,int n)

{int i,j,k,t,e,arcnum;

printf("请输入图的类型0-无向图，1-有向图");

scanf("%d",&t);

for(i=0;i

for(j=0;j

if(i==j) G[i][j]=0; /*对角线的值置为0*/

else G[i][j]=MaxNum; /*其它位置的值初始化为一个最大数*/

printf("请输入边(弧)的条数(%d-%d):",n-1,n*(n-1)/(2-t));

scanf("%d",&arcnum);

printf("请输入边的信息,按照起点(1-5) 终点(1-5) 权值的形式输入:\n");

for(k=0;k

{scanf("%d %d %d",&i,&j,&e);

if(t==0) G[j-1][i-1]=G[i-1][j-1]=e;

else G[i-1][j-1]=e;

}

}

/*弗洛伊德算法*/

void Floyd(int G[m][m], int A[m][m], int P[m][m],int n) {

int i, j, k;

for (i=0; i

for(j=0;j

{A[i][j]=G[i][j];P[i][j]=0;}

for (k=0; k

for (i=0; i

for (j=0; j

if(A[i][k] +A[k][j]

{ A[i][j]=A[i][k]+A[k][j];

P[i][j]=P[i][k]*10+P[k][j]*10+k+1; }

}

void main(){

int i,j,n;

adjmatrix G,A,P;

printf("交通站点的个数(2-9)");

scanf("%d",&n);

CreatMatrix(G,n);

Floyd(G, A, P,n);

printf("原图的临界矩阵\n");

for(i=0;i

{for(j=0;j

printf("%3d",G[i][j]);

printf("\n");}

printf("两点间的距离\n");

for(i=0;i

{for(j=0;j

printf("%3d",A[i][j]);

printf("\n");}

printf("两点间路径的中介点\n");

for(i=0;i

{for(j=0;j

printf("%3d",P[i][j]);

printf("\n");}

}