数据结构课程设计大作业XXXXXX班 题 目 最短路径问题 专 业 计算机科学与技术 学生姓名 XX 学 号 XXXXXXXX 指导教师 唐国民 樊艳芬 完成日期 2011.12.25 湖州师院信息与工程学院目录目录1最短路径问题2【内容摘要】2【关键字】2【Abstract】2【Key words】3实验内容概述1实验目的概述1解题思路的描述1源程序清单2程序调试及测试结果5结论7参考文献7最短路径问题【内容摘要】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：l 确定起点的最短路径问题- 即已知起始结点，求最短路径的问题。适合使用迪杰斯特拉算法。 l 确定终点的最短路径问题- 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 l 确定起点终点的最短路径问题- 即已知起点和终点，求两结点之间的最短路径。 l 全局最短路径问题- 求图中所有的最短路径。适合使用Floyd-Warshall算法。鉴于本题是求任意两点之间的最短路径，故使用弗洛伊德算法最为适合。【关键字】 最短路径 图论 弗洛伊德算法【Abstract】The shortest path problem in the study of graph theory is a classic algorithm, which is looking for figure (by node and path of the shortest path between two nodes. The form of specific algorithm including:l Sure the start point of the shortest path problem-that is known start node, for the shortest path problem. Suitable for use Dijkstra algorithm.l To determine the shortest path problem-and determine the starting point is the opposite, this problem is known to end nodes, for the shortest path problem. In the absence of this problem and to chart the start point of the question completely equivalent to determine, in the problem to figure in the equivalent to the total path direction the reversal of the starting point to determine the problem.l Sure start the end of the shortest path problem-that is known beginning and end, for the shortest path between two nodes.l Global the shortest path problem-pray for all the shortest path in the graph. Suitable for use Floyd-Warshall algorithm.In view of the subject is to ask for any of the shortest path between two points, it is most suitable for use of Floyd.【Key words】Shortest path，Graph theory，Floyd algorithm实验内容概述 这是一幅美国硅谷的简单地图。对于此图，请写出一个完整的程序，对于输入的起点和终点，输出它们之间的最短路径。实验目的概述在实际生活中诸如在运输路线、出外旅游路线、厂址选择等诸多方面都会有最短距离的应用。本实验中的问题是求任意两点间最短距离的问题，而实验的目的是运用邻接矩阵解决图存储并解决在此结构情况下对矩阵中元素的扫描计算。其关键是怎样储存和计算。储存用的是邻接矩阵，而计算用的是弗洛伊德算法。通过该实验更好地体会并进一步认识邻接矩阵，知道弗洛伊德算法在解决任意两点之间最短距离问题方面上的优势。解题思路的描述本题是求美国硅谷中任意两点之间的最短距离，首先考虑到弗洛伊德算法，并且需要用到邻接矩阵来解决存储问题。源程序清单#include#include#include#define fi 99999#define MAXVEX 20struct nodeint num;string name;xuhao17;void Floyed(int costMAXVEX,int n,int m,int x) int AMAXVEXMAXVEX,pathMAXVEXMAXVEX; int i,j,k,pre; for(i=0;in;i+) for(j=0;jn;j+) Aij=costij; pathij=-1; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;j(Aik+Akj) Aij=Aik+Akj; pathij=k; if(m!=x) cout xuhaom.name xuhaox.name ; if(Amx=fi) if(m!=x) cout 该路径不存在n endl; else cout 最短路径长度是: Amx 米n; cout 具体路径为: xuhaom.name -; pre=pathmx; while(pre!=-1) coutxuhaopre.name -; pre=pathprex; coutxuhaox.nameendl; void main() int i,k,l,x; cout 美国硅谷地图最短路线查询表: endl; cout -序号 - 地点名称 - endl; cout 0 San Rapheal endl; cout 1 Cross endl; cout 2 Daly Cit endl; cout 3 San Francisco endl; cout 4 Oakland endl; cout 5 San Larenzo endl; cout 6 Cross B endl; cout 7 San Maleo endl; cout 8 Hayward endl; cout 9 Dubin endl; cout 10 Redwood City endl; cout 11 Cross C endl; cout 12 Palo Also endl; cout 13 Freemood endl; cout 14 Min View endl; cout 15 Cupertin endl; cout 16 San Jose endl; coutendl; xuhao0.num=0;xuhao0.name=San Rapheal; xuhao1.num=1;xu