(H)图的遍历问题.doc

实验六 最短路径问题 需求分析 1.本程序要求从文件中读入有向网中顶点的数量和顶点间的票价的矩阵； 2.以用户指定的起点和终点，输出从起点到终点的花费； 3.用Dijkstra算法计算点对点的最短路径； 4.在Dos界面输出起点到终点的花费。 5.测试数据 输入 （文件） 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 概要设计 抽象数据类型 typedef struct GraphNode //图的结点 { int n; Mark m; //节点的状态 访问 还是未被访问 } GraphNode; typedef struct Graph //图 { int n; GraphNode * Node; int** edge; //边权信息 } Graph; 算法思想 网络信息。 输入和边权值存储边权值 建一个数组存储长度。 最短路径长度 最短路径和边值起点和长度。 { int n; Mark m; //是否被访问 } GraphNode; typedef struct Graph //图 { int n; GraphNode * Node; int** edge; //边权值 } Graph; Mark getMark(Graph*G , int i) //返回是否被访问 { return G-Node[i].m; } void setMark(Graph*G,int v,Mark m) //标记为已访问 { G-Node[v].m=m; } int first(Graph*G , int v) //第一个邻结点 { int i; for(i=0 ; iG-n ; i++) if((G-edge[v][i])!=-1) return i; return i; } int next(Graph*G , int v , int w) //下一个邻结点 { int i; for(i=w+1 ; iG-n ; i++) if((G-edge[v][i])!=-1) return i; return i; } int weight(Graph*G,int v,int w) //返回边权值 { return G-edge[v][w]; } int minVertex(Graph*G , int *D) ///寻找路径长度最短的那个顶点 { int i , v; for(i=0; iG-n; i++) if(getMark(G,i)==UNVISITED) { v=i; break; } for(i++; iG-n; i++) if(getMark(G,i)==UNVISITED((((D[i]D[v])D[i]!=-1)||(D[v]==-1)))) v=i; return v; } void Dijkstra(Graph*G , int *D , int s) //Dijkstra算法 { int i,v,w; for(i=0; iG-n; i++) { v=minVertex(G,D); if(D[v]==-1) return; //顶点v的路径长度小于0，即还处于初始状态，还未处理任何顶点，返回 setMark(G,v,VISITED); for(w=first(G,v); wG-n; w=next(G,v,w)) if((D[w](D[v]+weight(G,v,w)))||(D[w]==-1)) D[w]=D[v]+weight(G,v,w); } } 算法流程 输入模块： 输入顶点的数量，再输入各条弧（无边相连的权值 输出最短路径长度 （等待用户输入数和边权值） ： ： 五、#incl