下载文档原格式
【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括：①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题．②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题．③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径．④全局最短路径问题 - 求图中所有的最短路径．【问题原型】“将军饮马”，“造桥选址”，“费马点”．【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”．【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等．【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．【十二个基本问题】【问题1】作法图形原理连AB，与l交点即为P．两点之间线段最短．PA+PB 最小值为 AB．在直线l上求一点P，使PA+PB 值最小．【问题2】“将军饮马”作法图形原理作B关于l的对称点B＇两点之间线段最短．连A B＇，与l交点即为P．PA+PB 最小值为 A B＇．在直线l上求一点P，使PA+PB 值最小．【问题3】作法图形原理分别作点P关于两直线的两点之间线段最短．对称点P＇和P＇，连P＇P＇，PM+MN+PN 的最小值为在直线l1、l2上分别求点与两直线交点即为M，N．线段P＇P＇＇的长．M、N，使△PMN 的周长最小．【问题4】作法图形原理分别作点Q、P关于直线两点之间线段最短．l1、 l2的对称点Q＇和P＇四边形PQMN周长的最小连Q＇P＇，与两直线交点即值为线段P＇P＇＇的长．在直线l1、l2上分别求点为M，N．M 、N ，使四边形 PQMN的周长最小．- 1 -【问题5】“造桥选址”作法图形原理将点A向下平移MN的长两点之间线段最短．度单位得A＇，连A＇B，交nAM+MN+BN 的最小值为于点N，过N作NM⊥ m于直线m∥ n，在m、n，A＇B+MN．M．上分别求点M、N，使MN⊥ m，且AM+MN+BN的值最小．【问题6】作法图形原理将点A向右平移a个长度单位得A＇，作A＇关于l 两点之间线段最短．的对称点A＇＇，连A＇＇B，交AM+MN+BN 的最小值为在直线l上求两点M、N（M 直线l于点N，将N点向A＇＇B+MN．在左），使MN=a，并使左平移a个单位得M．AM+MN+NB 的值最小．【问题7】作法图形原理作点P关于l1的对称点点到直线，垂线段最短．2于B，交PA+AB PP＇，作 P＇B⊥l 的最小值为线段＇在l1上求点A，在l2上求l2于A．B的长．点B，使PA+AB值最小．【问题8】作法图形原理作点A关于l2的对称点两点之间线段最短．A＇，作点 B 关于l1的对AM+MN+NB 的最小值为A 为l1上一定点，B 为l2上称点B＇，连A＇B＇交l2于线段A＇B＇的长．一定点，在l2上求点M，M，交l1于 N．在l1上求点N，使AM+MN+NB 的值最小．【问题9】作法图形原理垂直平分上的点到线段两连AB，作AB的中垂线与端点的距离相等．在直线l上求一点P，使直线l的交点即为P．PA - PB ＝0．PA - PB 的值最小．、【问题10】作法图形原理三角形任意两边之差小于作直线AB，与直线l的交第三边．PA - PB ≤AB．在直线l上求一点P，使点即为P．PA - PB 的最大值＝AB．PA - PB 的值最大．【问题11】作法图形原理三角形任意两边之差小于作B关于l的对称点B＇第三边．PA - PB ≤AB＇．作直线A B＇，与l交点即在直线l上求一点P，使为P．PA - PB 最大值＝AB＇．PA - PB 的值最大．【问题12】“费马点”作法图形原理所求点为“费马点”，即满足∠APB＝∠BPC＝∠APC＝120°．以 AB、AC 两点之间线段最短．为边向外作等边△ABD、PA+PB+PC 最小值＝CD．△ABC中每一内角都小于△ACE，连CD、BE相交120°，在△ABC内求一点于P，点P即为所求．P，使 PA+PB+PC 值最小．【精品练习】1．如图所示，正方形ABCD的面积为12，△ABE是等边三角形，点E在正方形ABCD内，在对角线AC上有一点P，使PD+PE的和最小，则这个最小值为（）A D A．2 3 B．2 6 C．3D． 6 PEB C2．如图，在边长为 2 的菱形ABCD中，∠ABC＝60°，若将△ACD绕点A旋转，当AC′、AD′分别与BC、CD 交于点E、F，则△CEF的周长的最小值为（）A．2 B．2 3C．2+ 3 D．4- 3 -3．四边形 ABCD 中，∠B ＝∠D ＝90°，∠C ＝70°，在 BC 、CD 上分别找一点 M 、N ，使△AMN 的周长最小时， ∠AMN +∠ANM 的度数为（ ）A ．120°B ．130°C ．110°D ．140°4．如图，在锐角△ABC 中，AB ＝4 2 ，∠BAC ＝45°，∠BAC 的平分线交 BC 于点 D ，M 、N 分别是 AD 和 AB上的动点，则 BM +MN 的最小值是．5．如图，Rt △ABC 中，∠C ＝90°，∠B ＝30°，AB ＝6，点 E 在 AB 边上，点 D 在 BC 边上（不与点 B 、C 重合），且 ED ＝AE ，则线段 AE 的取值范围是 ．6．如图，∠AOB ＝30°，点 M 、N 分别在边 OA 、OB 上，且 OM ＝1，ON ＝3，点 P 、Q 分别在边 OB 、OA 上，则 MP ＋PQ ＋QN 的最小值是_________．（注“勾股定理”：直角三角形中两直角边的平方和等于斜边的平方，即 Rt △ABC 中，∠C ＝90°，则有 AC 2 + BC 2 = AB 2）7．如图，三角形△ABC 中，∠OAB ＝∠AOB ＝15°，点 B 在 x 轴的正半轴，坐标为 B ( 6 3 ，0)．OC 平分∠AOB ，点 M 在 OC 的延长线上，点 N 为边 OA 上的点，则 MA ＋MN 的最小值是______．- 4 -8．已知A（2，4）、B（4，2）．C在y轴上，D在x轴上，则四边形ABCD的周长最小值为，此时C、D两点的坐标分别为．9．已知A（1，1）、B（4，2）．（1）P为x轴上一动点，求PA+PB的最小值和此时P点的坐标；（2）P为x轴上一动点，求PA PB的值最大时P点的坐标；（3）CD为x轴上一条动线段，D在C点右边且CD＝1，求当AC+CD+DB的最小值和此时C点的坐标；10．点C为∠AOB内一点．（1）在OA求作点D，OB上求作点E，使△CDE的周长最小，请画出图形；（2）在（1）的条件下，若∠AOB＝30°，OC＝10，求△CDE周长的最小值和此时∠DCE的度数．- 5 -。
最短路径的实验报告最短路径的实验报告引言：最短路径问题是图论中一个经典的问题，涉及到在一个带有权重的图中找到两个顶点之间的最短路径。
本实验旨在通过实际操作和算法分析，深入探讨最短路径算法的性能和应用。
实验设计：本次实验使用了Dijkstra算法和Floyd-Warshall算法来解决最短路径问题。
首先，我们使用Python编程语言实现了这两个算法，并对它们进行了性能测试。
然后，我们选择了几个不同规模的图进行实验，以比较这两种算法的时间复杂度和空间复杂度。
最后，我们还在实际应用中使用了最短路径算法，以验证其实用性。
实验过程：1. 实现Dijkstra算法Dijkstra算法是一种贪心算法，用于求解单源最短路径问题。
我们首先实现了该算法，并对其进行了性能测试。
在测试中，我们使用了一个包含1000个顶点和5000条边的图，记录了算法的运行时间。
结果显示，Dijkstra算法的时间复杂度为O(V^2)，其中V表示图中的顶点数。
2. 实现Floyd-Warshall算法Floyd-Warshall算法是一种动态规划算法，用于求解所有顶点对之间的最短路径。
我们在Python中实现了该算法，并对其进行了性能测试。
在测试中，我们使用了一个包含100个顶点和5000条边的图，记录了算法的运行时间。
结果显示，Floyd-Warshall算法的时间复杂度为O(V^3)，其中V表示图中的顶点数。
3. 比较两种算法通过对Dijkstra算法和Floyd-Warshall算法的性能测试，我们可以看到，Dijkstra算法在处理较大规模的图时性能更好，而Floyd-Warshall算法在处理较小规模的图时性能更好。
因此，在实际应用中，我们可以根据图的规模选择合适的算法。
4. 应用实例为了验证最短路径算法的实际应用性，我们选择了一个城市交通网络图进行实验。
我们使用了Dijkstra算法来计算两个城市之间的最短路径，并将结果与实际的驾车时间进行比较。
最短路径实验报告最短路径实验报告引言：最短路径算法是计算机科学中的一个经典问题，它在许多领域中都有广泛的应用，如交通规划、电路设计、网络通信等。
本实验旨在通过实践探索最短路径算法的实际应用，并对其性能进行评估。
一、问题描述：我们将研究一个城市的交通网络，其中包含多个节点和连接这些节点的道路。
每条道路都有一个权重，表示通过该道路所需的时间或距离。
我们的目标是找到两个节点之间的最短路径，即使得路径上各个道路权重之和最小的路径。
二、算法选择：为了解决这个问题，我们选择了Dijkstra算法和Floyd-Warshall算法作为比较对象。
Dijkstra算法是一种单源最短路径算法，它通过不断选择当前最短路径的节点来逐步扩展最短路径树。
Floyd-Warshall算法则是一种多源最短路径算法，它通过动态规划的方式计算任意两个节点之间的最短路径。
三、实验设计：我们首先构建了一个包含10个节点和15条道路的交通网络，每条道路的权重随机生成。
然后，我们分别使用Dijkstra算法和Floyd-Warshall算法计算两个节点之间的最短路径，并记录计算时间。
四、实验结果：经过实验，我们发现Dijkstra算法在计算单源最短路径时表现出色，但是在计算多源最短路径时效率较低。
而Floyd-Warshall算法在计算多源最短路径时表现出色，但是对于大型网络的单源最短路径计算则需要较长的时间。
五、性能评估：为了评估算法的性能，我们对不同规模的交通网络进行了测试，并记录了算法的计算时间。
实验结果显示，随着交通网络规模的增大，Dijkstra算法的计算时间呈指数级增长，而Floyd-Warshall算法的计算时间则呈多项式级增长。
因此，在处理大型网络时，Floyd-Warshall算法具有一定的优势。
六、实际应用：最短路径算法在实际应用中有着广泛的用途。
例如，在交通规划中，最短路径算法可以帮助我们找到最优的行车路线，减少交通拥堵。
云南财经大学信息学院学生综合性与设计性实验报告（2013—2014 学年第 2 学期）一、实验内容与目的1.内容查看“最短路径.swf”，选择熟悉的程序设计语言定义有向图，根据动画演示求取从有向图任一结点到其他结点的最短路径。
2.实验目的了解最短路径的概论，掌握求最短路径的方法。
二、实验原理或技术路线（可使用流程图描述）实验原理：(李燕妮负责设计，周丽琼负责编程)图是由结点的有穷集合V和边的集合E组成，求最短路径用迪杰斯特拉算法：1)适用条件&范围：a) 单源最短路径(从源点s到其它所有顶点v);b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)c) 所有边权非负(任取(i,j)∈E都有Wij≥0);2)算法描述：a)初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s};b)For i:=1 to n1.取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S}2.S=S+{u}3.For V-S中每个顶点v do Relax(u,v,Wu,v)c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点三、实验环境条件（使用的软件环境）Microsoft Visual C++6.0四、实验方法、步骤（列出程序代码或操作过程）/*本程序的功能是求图中任意两点间的最短路径*/#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>#define ING 9999typedef struct ArcCell{int adj;/*顶点关系类型，用1表示相邻，0表示不相邻*/}ArcCell,**AdjMatrix;/*邻接矩阵*/typedef struct type{char data[3];/*顶点值*/}VertexType;typedef struct{VertexType *vexs; /*顶点向量*/AdjMatrix arcs; /*邻接矩阵*/int vexnum,arcnum; /*图的顶点数和边数*/}MGraph;/*初始图*/void InitGraph(MGraph *G){int i,nu,mu;printf("\n输入顶点的个数和（边）弧的个数：");scanf("%d %d",&nu,&mu);G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *));for(i=0;i<nu;i++)/*分配邻接矩阵空间*/G->arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell));G->vexs=(VertexType *)malloc(nu*sizeof(VertexType)); /*分配顶点空间*/ G->vexnum=nu;G->arcnum=mu; /*图的顶点数和边数*/}void InsertGraph(MGraph *G,int i,VertexType e){if(i<0||i>G->vexnum) return;strcpy(G->vexs[i].data,e.data);}/*确定v1在图顶点中的位置*/int Locate(MGraph G,VertexType v1){int i;for(i=0;i<G.vexnum;i++)if(strcmp(v1.data,G.vexs[i].data)==0) return i;return -1;}/*采用数组（邻接矩阵）和邻接表表示无向图*/void CreateUND(MGraph *G){int i,j,k,*p,w;VertexType v1,v2;p=(int *)malloc(G->vexnum*sizeof(int));for(i=0;i<10;i++) p[i]=0;for(i=0;i<G->vexnum;++i) /*初始邻接表*/{for(j=0;j<G->vexnum;++j)G->arcs[i][j].adj=ING;}for(k=0;k<G->arcnum;++k){printf("\n输入第%d 条（边）弧相对的两个顶点值:\n",k+1);scanf("%s %s",v1.data,v2.data);/*输入相邻的两个点值*/printf("输入它们的权值: ");scanf("%d",&w);i=Locate(*G,v1);j=Locate(*G,v2); /*用i 和j来确定它们的位置*/G->arcs[i][j].adj=w;}}/*输出邻接矩阵*/void Pint(MGraph G){int i,j;for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){if(G.arcs[i][j].adj!=ING)printf("\t%d",G.arcs[i][j].adj);else{if(i==j)printf("\t0");else printf("\t∞");}}printf("\n");}}/*对顶点V0到其余顶点v的最短路径p[v]及其带权长度D[v]若p[v][w]为1，则w是从V0到W当前求得最短路径上的顶点, final[v]为1，当且仅当v属于S，即已经求得从v0到v的最短路*/void ShortestPath(MGraph G,int v0,int **p,int *D){int v,u,i,w,min;int *final;final=(int *)malloc(G.vexnum*sizeof(int));/*分配空间*/for(v=0;v<G.vexnum;++v){final[v]=0;D[v]=G.arcs[v0][v].adj;/*初始化*/for(w=0;w<G.vexnum;++w) p[v][w]=0;/*设空路径*/if(D[v]<ING){p[v][v0]=1;p[v][v]=1;}/*v到v0有路径*/}D[v0]=0;final[v0]=1;/*初始化，V0顶点属于S集*/for(i=1;i<G.vexnum;i++){/*其余G.vexnum-1个顶点*/min=ING;for(w=0;w<G.vexnum;++w) /*求出矩阵这一行的最小值*/ if(!final[w]) /*W顶点属于V-S中*/if(D[w]<min){v=w;min=D[w];}final[v]=1;/*离V0顶点最近的V加入S集*/for(w=0;w<G.vexnum;++w) /*更新当前最短路径及距离*/ if(!final[w]&&(min+G.arcs[v][w].adj<D[w])){ /*不是最小的，修改D[w],P[w]*/D[w]=min+G.arcs[v][w].adj;for(u=0;u<G.vexnum;u++)p[w][u]=p[v][u];p[w][w]=1;}}free(final);}void main(){MGraph G;VertexType e;int i,j;int **p;int *D;InitGraph(&G);p=(int **)malloc(G.vexnum*sizeof(int *));for(i=0;i<G.vexnum;i++)p[i]=(int *)malloc(G.vexnum*sizeof(int));D=(int *)malloc(G.vexnum*sizeof(int));printf("顶点值：\n");for(i=0;i<G.vexnum;++i)/*给图顶点向量付值*/{scanf("%s",e.data);InsertGraph(&G,i,e);}CreateUND(&G);/*构造图结构*/printf("邻接矩阵为：\n");Pint(G);for(i=0;i<G.vexnum;i++) /*输出邻接矩阵*/{ShortestPath(G,i,p,D); /*调用最短函数*/for(j=0;j<G.vexnum;j++)if(i!=j) printf(" %s 到%s 的最短路径为%d \n",G.vexs[i].data,G.vexs[j].data,D[j]);printf("\n\n");}getch();}五、实验过程原始记录( 测试数据、图表)请给出各个操作步骤的截图和说明，要求有对时间复杂度和空间复杂度的说明。
HUNAN UNIVERSITY 课程实习报告题目最短路径问题学生姓名学生学号专业年级指导老师完成日期一、需求分析本实验是求最短路径的问题，从文件中读入有向网中顶点的数量和顶点间的票价的矩阵，以用户指定的起点，在文件中输出到其余各顶点的最短路径及花费。
（1）输入：输入的形式：（文件）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输入值的范围：文件输入中，顶点数和矩阵中顶点间的票价均为整型int，用户输入中，起点数为整型int。
（2）输出的形式：（文件）源点0到顶点1的最小花费为:5路径为：0——>2——>1源点0到顶点2的最小花费为:3路径为：0——>2源点0到顶点3的最小花费为:10路径为：0——>2——>1——>3源点0到顶点4的最小花费为:18路径为：0——>2——>4（3）程序所达到的功能：在文件中给出有向网的顶点个数和顶点间的票价的矩阵，以用户指定的起点，在文件中输出起点到其余各顶点的最短路径及花费。
（4）测试数据：a.输入：（文件）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输出：（文件）源点0到顶点1的最小花费为:5路径为：0——>2——>1源点0到顶点2的最小花费为:3路径为：0——>2源点0到顶点3的最小花费为:10路径为：0——>2——>1——>3源点0到顶点4的最小花费为:18路径为：0——>2——>4b.输入：（文件）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（用户）输入起点：2输出：（文件）源点2到顶点0：没有连通路径源点2到顶点1的最小花费为:2路径为：2——>1源点2到顶点3的最小花费为:7路径为：2——>1——>3源点2到顶点4的最小花费为:15路径为：2——>4c.输入：（文件）618 10 3 20 -1 915 -1 -1 5 -1 -1-1 20 16 -1 -1 15-1 -1 30 -1 6 32 9 -1 20 -1 -1-1 8 12 -1 -1 5（用户）输入起点：5输出：（文件）源点5到顶点0的最小花费为:21路径为：5——>1——>3——>4——>0源点5到顶点1的最小花费为:8路径为：5——>1源点5到顶点2的最小花费为:12路径为：5——>2源点5到顶点3的最小花费为:13路径为：5——>1——>3源点5到顶点4的最小花费为:19路径为：5——>1——>3——>4d.输入：（文件）618 10 3 20 -1 915 -1 -1 5 -1 -1-1 20 16 -1 -1 15-1 -1 30 -1 6 32 9 -1 20 -1 -1-1 8 12 -1 -1 5（用户）输入起点：3输出：（文件）源点3到顶点0的最小花费为:8路径为：3——>4——>0源点3到顶点1的最小花费为:11路径为：3——>5——>1源点3到顶点2的最小花费为:11路径为：3——>4——>0——>2源点3到顶点4的最小花费为:6路径为：3——>4源点3到顶点5的最小花费为:3路径为：3——>5e.输入：（文件）3-1 -1 -1-1 -1 -1-1 -1 -1（用户）输入起点：1输出：（文件）源点1到顶点0：没有连通路径源点1到顶点2：没有连通路径f.输入：（文件）3-1 -1 -1-1 -1 -1-1 -1 -1（用户）输入起点：3输出：（文件）源点3到顶点0的最小花费为:-572562307路径为：3——>1——>0源点3到顶点1的最小花费为:-572662307路径为：3——>1源点3到顶点2的最小花费为:-572662307路径为：3——>2二、概要设计（1）所有抽象数据类型的定义：const int MaxNum=100000;//利用邻接矩阵存储图：class Graph{private:int *Adj;//保存邻接矩阵的一维数组j和k之间权值存储在Adj[j*Num+k]中int Num;public:Graph();~Graph();void Floyd(int start);};（2）算法的基本思想：采用邻接矩阵为图的存储结构，保存邻接矩阵的一维数组j和k之间权值存储Adj[j*Num+k]中，以用户指定的起点，进行弗洛伊德算法，先初始化最短路径，对角线元素设置为0，其他元素设置为边的权值，没有有向边设置为MaxNum，依次插入中间点k，判断是否检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，若不成立则路径不改变，若成立则更新最短路径，设置Dis(i,j) = Dis(i,k) + Dis(k,j)，直至循环结束，更新后的最短路径入栈，在文件中输出到其余各顶点的最短路径及花费。
最短路径算法及应用乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。
如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？一种可能的方法就是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。
那么我们很容易看到，即使不考虑包含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是不值得考虑的。
在这一章中，我们将阐明如何有效地解决这类问题。
在最短路径问题中，给出的是一有向加权图G＝（V，E，W），其中V为顶点集，E为有向边集，W为边上的权集。
最短路径问题研究的问题主要有：单源最短路径问题、与所有顶点对之间的最短路径问题。
一、单源最短路径问题所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V 到V中的每个结点的最短路径。
首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。
（一）Dijkstra算法对于图G，如果所有Wij≥0的情形下，目前公认的最好的方法是由Dijkstra于1959年提出来的。
例1 已知如下图所示的单行线交通网，每弧旁的数字表示通过这条单行线所需要的费用，现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。
Dijkstra方法的基本思想是从vs出发，逐步地向外探寻最短路。
执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P 标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。
在叙述Dijkstra方法的具体步骤之前，以例1为例说明一下这个方法的基本思想。
例1中，s=1。
因为所有Wij≥0，故有d(v1, v1)=0。
一、概述 (1)二、....................... 系统分析1三、....................... 概要设计2四、....................... 详细设计54.1建立图的存储结构 (5)4.2单源最短路径 (6)4.3任意一对顶点之间的最短路径 (7)五、运行与测试 (8)参考文献 (11)附录12交通咨询系统设计（最短路径问题）一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。
在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。
这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。
二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径（里程）、最低花费或是最少时间等问题。
对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。
针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。
并未本系统设置一人性化的系统提示菜单，方便使用者的使用。
二、概要设计可以将该系统大致分为三个部分：①建立交通网络图的存储结构；②解决单源最短路径问题；③实现两个城市顶点之间的最短路径问题。
交通咨询系统迪杰斯特拉算法（单源最短路径）费洛依德算法（任意顶点对间最短路迪杰斯特拉算法流图:弗洛伊德算法流图:四、详细设计4.1建立图的存储结构定义交通图的存储结构。
邻接矩阵是表示图形中顶点之间相邻关系的矩阵。
设G=(V,E)是具有n个顶点的图，贝S G的邻接矩阵是具有如下定义的n阶方阵。
