实验四图的最短路径弗洛伊德算法实现.doc

数据结构与算法课程实验报告 实验四：图的相关算法应用 姓名：王连平 班级：09信科2班 学号：实验四 图的相关算法应用 一、实验内容 求有向网络中任意两点之间的最短路。 二、实验目的 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 三、问题从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 四、问题的实现 4.1数据结构的抽象数据类型定义和说明 1） typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info;//此项用来保存弧信息，，在本实验中没有相关信息要保存 }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; 顶点信息和弧信息都是用来建立一个有向网G 2） d[v][w];//G中各对顶点的带权长度 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点 4.2主要的实现思路 首先通过一个函数（CreateDN）建立图的邻接矩阵储存方式,一次输入某条弧的起点，终点，和权值。通过调用Locate函数来找到该弧在邻接矩阵中的相应位置。 其次运用弗洛伊德算法来求各定点的最短路劲，具体思路为：如果从v到w有弧，则存在一条长度为arcs[v][w]的路径，该路径不一定是最短路径。考虑路径（v,u,w）是否存在，若存在，比较（v,w）和（v,u,w）的长度，取较短者为从v到w的中间点序号不大于0的最短路径。以此类推，每次增加一个点，从而求出任意两点间的最短路径。这样，经过n次比较后，所求得的必为从v到w的最短路径。按此方法，可以同时求得任意两点间的最短路径。 五、主要源程序代码（包含程序备注） #includeiostream #includestring using namespace std; #define INfinity 10000//最大值 # define MAX_VERTEX_NUM 10//最大顶点数 typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info; }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; int Locate(MGraph G,string v) { int a=0; for (int i=0;iG.vexnum;i++) { if( G.vexs[i]==v) { a=i; break;} } return a; } void CreateDN(MGraph G)//采用邻接矩阵表示法，构造有向图G { string v1,v2; int w; cout请依次输入图的顶点数和弧数endl; cinG.vexnumG.arcnum; for (int i=0;iG.vexnum;i++) { cout请按顺序输入地点endl; cinG.vexs[i]; } for (int i=0;iG.vexnum;i++)//初始化邻接矩阵； { for (int j=0;jG.vexnum;j++) G.arcs[i][j].Distance=INfinity;} for (int k=0;kG.arcnum;k++){ cout请输入某条路径的初始地点V1,终点V2及他们之间的距离Wendl; cinv1v2w; int i=Locate(G,v1); int j=Locate(G,v2); G.arcs[i][j].Distance=w; } } void Floyd(MGr