《数据结构》实验报告 ◎实验题目: 求最短路径。 ◎实验内容:求图中任意两点间的最短路径。 一、需求分析 程序目的是求有向图中任意两点间的最短路径。 1、由用户指定图中任意两点。 2、输出结果为指定两点间的最短路径。 二 概要设计 1、定义结构体 typedef struct ArcNode//节点类型 { int adjvex; struct ArcNode *nextarc; InfoType_Cost cost; InfoType_Length length; }ArcNode; typedef struct VNode//城市编号 { int No; VertexType city[15]; ArcNode *firstarc; }VNode,AdjList[MAX_VERTX_NUM]; typedef struct ALGraph//图 { AdjList vertices; int vexnum; int arcnum; }ALGraph; typedef struct str1 { int value_D; int flag_S; }D[20]; typedef struct str2 { int father; }P[20]; 2.定义函数 void Analyse_Info() 操作结果:读入文件,将信息存入数组 ALGraph Create_Graph() 操作结果:创建一个图 void ShortPath_DIJ(ALGraph G,int v_sou) 初始条件:已知图G; 操作结果:用Dijkstra 算法求任意两点之间最短路径。 void InfoCustomer(ALGraph G,str2 p[],str1 d[],int v_sou,int v_des,int method) 操作结果:将最短路径结果呈现给用户。 三 详细设计 #define INT_MAX 65534 #define INFINITY INT_MAX #define MAX_VERTX_NUM 20 #define FALSE -1 #define TRUE 1 typedef char VertexType; typedef int InfoType_Cost; typedef int InfoType_Length; typedef struct ArcNode//节点类型 { int adjvex; struct ArcNode *nextarc; InfoType_Cost cost; InfoType_Length length; }ArcNode; typedef struct VNode//城市编号 { int No; VertexType city[15]; ArcNode *firstarc; }VNode,AdjList[MAX_VERTX_NUM]; typedef struct ALGraph { AdjList vertices; int vexnum; int arcnum; }ALGraph; typedef struct str1 { int value_D; int flag_S; }D[20]; typedef struct str2 { int father; }P[20]; int arcnum=0,vexnum=0; char city[20][15]; int path[52],cost[52]; char city_1[52][20],city_2[52][20]; P Path_cost,Path_len; D Dear_cost,Dear_len; void Analyse_Info()//读入文件,将信息存入数组 { FILE *fp; int i=0,j=0,k=0; i...