求解最优交通路径

1、求解最优交通路径C程 序 设 计求解最优交通路径求解最优交通路径在程序中预置部分城市间的距离，然后由用户选择两个城市，计算出两城市之间的最短距离以及相应的路线。CONTENTS01编程思路分析基础知识点具体实现总结030204编程思路分析1.编程思路分析定义CreateUDN() 函数，根据用户输入的顶点数和边数生成一个相应的交通图，其中顶点对应于城市，边对应于城市间的直接通路。定义narrate() 函数输出能够进行计算的城市列表。定义函数ShortestPath() 计算城市间的最短路径。定义函数output()用于输出城市间的最短路径。在主函数中调用以上各函数以实现程序功能。基础知识点图

2、(Graph)是一种比线性表和树更为复杂的数据结构。线性结构：研究数据元素之间的一对一关系，在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的直接前驱和直接后继。图结构：研究数据元素之间的多对多关系，在这种结构中，任意两个元素之间可能存在关系，即结点之间的关系可以是任意的，图中任意元素之间都可能相关。图：记为 G( V, E ) 其中：V是G的顶点集合，是有穷非空集； E是G的边集合，是有穷集。V=vertex E=edge2.基础知识点有向图：图G中的每条边都是有方向的。无向图：图G中的每条边都是无方向的。G2=(V2,E2)V2=A, B, C, D, E,FE2 =(A, B

3、), (A, E),(B, E), (B, F), (C, D), (C, F), (D, F)G1 = (V1, E1)V1=A, B, C, D, EE1=, , , , , , BCAFEDG2:G1:EACBD2.基础知识点图的邻接矩阵表示：BACDFEAij=0 (i,j)E1 (i,j)E定义: 矩阵的元素为ABCDEFABCDEF0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 无向图：2.基础知识点对称矩阵ABECD有向图:0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1

4、 1 0 0 0 0 0 1 0 0 ABCDE图的邻接矩阵表示：ABCDE2.基础知识点非对称矩阵带权图（网）的邻接矩阵表示：以有向网为例：Aij= (i,j)Ewij (i,j)E定义: 矩阵的元素为AABCDEABECD20152518101020BCED2.基础知识点2.基础知识点 Dijkstra(迪杰斯特拉)算法Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法思想：设G=(V,E)是一个带权图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始

5、时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。2.基础知识点 Dijkstra(迪杰斯特拉)算法算法步骤：（1）初始时，S只包含源点，即Sv，v的距离为0。U包含除v外的其他顶点，即:U=其余顶点，若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为。（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距

6、离就是v到k的最短路径长度）。（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。（4）重复步骤（2）和（3）直到所有顶点都包含在S中。具体实现总结4.总结本例中，用图表示城市交通网络。图的一般形式记为 G( V, E )，其中：V是G的顶点集合，E是G的边集合。根据图的每条边是否有方向可将图分为有向图和无向图，有向图和无向图均可用邻接矩阵来表示。若图中每条边均带有权重，则为带权图。本例中的城市交通网络图就是一个带权图，权重为两城市之间的距离。Dijkstra(迪杰斯特拉)算法是典型的最短路径算法，用于计算一个节点到其他所有节点的最