下载文档原格式
最短路径问题的优化算法最短路径问题是计算网络中两个节点之间最短路径的一个经典问题。
在许多实际应用中，如导航系统、交通规划和物流管理等领域，寻找最短路径是一个重要的任务。
然而，当网络规模较大时，传统的最短路径算法可能会面临计算时间长、耗费大量内存等问题。
为了解决这些问题，研究人员提出了许多优化算法，以提高最短路径问题的计算效率。
一、Dijkstra算法的优化Dijkstra算法是最短路径问题中最经典的解法之一，但当网络中的节点数量较大时，其计算时间会显著增加。
为了优化Dijkstra算法，研究者提出了以下几种改进方法：1. 堆优化Dijkstra算法中最耗时的操作是从未访问节点中选取最短路径的节点。
传统的实现方式是通过线性搜索来选择下一个节点，时间复杂度为O(N)，其中N是节点的数量。
而使用堆数据结构可以将时间复杂度降低到O(lgN)，从而提高算法的效率。
2. 双向Dijkstra算法双向Dijkstra算法是通过同时从起点和终点开始搜索，以减少搜索的范围和时间。
在搜索过程中，两个搜索方向逐渐靠近，直到找到最短路径为止。
双向Dijkstra算法相比传统的Dijkstra算法能够减少搜索空间，因此在网络规模较大时可以提供更快的计算速度。
二、A*算法A*算法是一种启发式搜索算法，常用于解决最短路径问题。
与传统的Dijkstra算法不同，A*算法通过引入启发函数来优先搜索距离终点较近的节点。
启发函数的选择对算法的效率有重要影响，一般需要满足启发函数低估距离的性质。
A*算法的时间复杂度取决于启发函数，如果启发函数选择得恰当，可以在大规模网络中快速找到最短路径。
三、Contraction Hierarchies算法Contraction Hierarchies（CH）算法是近年来提出的一种高效解决最短路径问题的方法。
CH算法通过预处理网络，将网络中的节点进行合并，形成层次结构。
在查询最短路径时，只需在层次结构上进行搜索，大大减少了计算复杂度。
实验三最短路径的算法（离散数学实验报告）实验3：最短路径算法⼀、实验⽬的通过本实验的学习，理解Floyd（弗洛伊得）最短路径算法的思想⼆、实验内容⽤C语⾔编程实现求赋权图中任意两点间最短路径的Floyd算法，并能对给定的两结点⾃动求出最短路径三、实验原理、⽅法和⼿段1、Floyd算法的原理定义：Dk[i,j] 表⽰赋权图中从结点vi出发仅通过v0，v1，┉，vk-1中的某些结点到达vj的最短路径的长度，若从vi到vj没有仅通过v0，v1，┉，vk-1 的路径，则D[i,j]=∝即D-1[i,j] 表⽰赋权图中从结点vi到vj的边的长度，若没有从结点vi到vj的边，则D[i,j]=∝D0[i,j] 表⽰赋权图中从结点vi到vj的”最短”路径的长度, 这条路上除了可能有v0外没有其它结点D1[i,j] 表⽰赋权图中从结点vi到vj的”最短”路径的长度, 这条路上除了可能有v0，v1外没有其它结点┉┉┉根据此定义，D k[i,j]=min{ D k-1[i,j] , D k-1[i,k-1]+D k-1[k-1,j] }定义：path[i,j]表⽰从结点vi到vj的“最短”路径上vi的后继结点四、实验要求要求输出每对结点之间的最短路径长度以及其最短路径五、实验步骤（⼀）算法描述Step 1 初始化有向图的成本邻矩阵D、路径矩阵path若从结点vi到vj有边，则D[i,j]= vi到vj的边的长度，path[i,j]= i；否则D[i,j]=∝，path[i,j]=-1Step 2 刷新D、path 对k=1,2,┉n 重复Step 3和Step 4Step 3 刷新⾏对i=1,2,┉n 重复Step 4Step 4 刷新Mij 对j=1,2,┉n若D k-1[i,k]+D k-1[k,j][结束循环][结束Step 3循环][结束Step 2循环]Step 5 退出（⼆）程序框图参考主程序框图其中，打印最短路径中间结点调⽤递归函数dist()，其框图如下，其中fist,end是当前有向边的起点和终点dist(int first, int end)七、测试⽤例：1、输⼊成本邻接矩阵：D ：06380532290141003210∝∝∝∝V V V V V V V V （其中∝可⽤某个⾜够⼤的数据值代替，⽐如100）可得最短路径矩阵：P ：131132122211111010103210--------V V V V V V V V以及各顶点之间的最短路径和最短路径长度：从V0到V1的最短路径长度为：1 ；最短路径为：V0→V1 从V0到V2的最短路径长度为：9 ；最短路径为：V0→V1→V3→V2 从V0到V3的最短路径长度为：3 ；最短路径为：V0→V1→V3 从V1到V0的最短路径长度为：11；最短路径为：V1→V3→V2→V0从V1到V2的最短路径长度为：8 ；最短路径为：V1→V3→V2 从V1到V3的最短路径长度为：2 ；最短路径为：V1→V3 从V2到V0的最短路径长度为：3 ；最短路径为：V2→V0 从V2到V1的最短路径长度为：4 ；最短路径为：V2→V0→V1 从V2到V3的最短路径长度为：6 ；最短路径为：V2→V0→V1→V3 从V3到V0的最短路径长度为：9 ；最短路径为：V3→V2→V0 从V3到V1的最短路径长度为：10；最短路径为：V3→V2→V0→V1 从V3到V2的最短路径长度为：6 ；最短路径为：V3→V2 参考程序： #include #define INFINITY 100 #define Max 10int a[Max][Max],P[Max][Max]; main() {void Print_Flod(int d);int i,j,k,D=4;printf("请输⼊成本邻接矩阵：\n");for(i=0;ifor(j=0;j{scanf("%d",&a[i][j]);}for(i=0;ifor(j=0;j{if(a[i][j]>0&& a[i][j]elseP[i][j]=-1;}for(k=0;kfor(i=0;ifor(j=0;jif (a[i][k]+a[k][j]{a[i][j]=a[i][k]+a[k][j];P[i][j]=k;}Print_Flod(D);}void Print_Flod(int d){void dist(int first,int end);int i,j;for(i=0;ifor(j=0;jif(i!=j){ printf("from V%d to V%d: ",i,j); dist(i,j);printf("V%d",j);printf(" (The length is: %d)\n",a[i][j]); }}void dist(int first,int end){ int x;x=P[first][end];if(x!=first){ dist(first,x); dist(x,end); }else printf("V%d->",x);}输出结果：。
【转】彻底弄懂最短路径问题（图论）P.S.根据个⼈需要，我删改了不少问题引⼊问题：从某顶点出发，沿图的边到达另⼀顶点所经过的路径中，各边上权值之和最⼩的⼀条路径——最短路径。
解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法，另外还有著名的启发式搜索算法A*，不过A*准备单独出⼀篇，其中Floyd算法可以求解任意两点间的最短路径的长度。
笔者认为任意⼀个最短路算法都是基于这样⼀个事实：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若⼲个节点到B。
⼀.Dijkstra算法该算法在《数据结构》课本⾥是以贪⼼的形式讲解的，不过在《运筹学》教材⾥被编排在动态规划章节，建议读者两篇都看看。
(1) 迪杰斯特拉(Dijkstra)算法按路径长度递增次序产⽣最短路径。
先把V分成两组：S：已求出最短路径的顶点的集合V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加⼊到S中，依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之和（反证法可证）。
(2) 求最短路径步骤1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值，若存在<V0,Vi>，为<V0,Vi>弧上的权值（和SPFA初始化⽅式不同），若不存在<V0,Vi>，为Inf。
2. 从T中选取⼀个其距离值为最⼩的顶点W(贪⼼体现在此处)，加⼊S(注意不是直接从S集合中选取，理解这个对于理解vis数组的作⽤⾄关重要)，对T中顶点的距离值进⾏修改：若加进W作中间顶点，从V0到Vi的距离值⽐不加W的路径要短，则修改此距离值（上⾯两个并列for循环，使⽤最⼩点更新）。
3. 重复上述步骤，直到S中包含所有顶点，即S=V为⽌（说明最外层是除起点外的遍历）。
导航系统中的路径规划算法导航系统是一种广泛应用的技术，它通过计算机算法帮助人们找到最佳路径。
而路径规划算法是导航系统中的核心部分，它决定了导航系统能否找到最优解。
本文将介绍导航系统中常用的路径规划算法，并分析各算法的优缺点。
一、最短路径算法最短路径算法是导航系统中最基本的算法之一，它的目标是找到两点之间最短的路径。
其中最著名的算法是迪杰斯特拉算法和弗洛伊德算法。
迪杰斯特拉算法通过动态规划的方式逐步计算出起点到终点的最短路径，运行时间复杂度为O(N^2)。
而弗洛伊德算法则通过多次迭代计算所有节点之间的最短路径，运行时间复杂度为O(N^3)。
两者各有优劣，具体应用根据实际情况选择。
二、A*算法A*算法是一种启发式搜索算法，它在最短路径算法的基础上引入了启发函数，能够更快地找到最优解。
A*算法的核心思想是综合考虑节点的实际代价和预估代价进行搜索。
实际代价是指起点到当前节点的代价，而预估代价则是根据启发函数估计当前节点到终点的代价。
通过不断更新节点的实际代价和预估代价，A*算法能够在很短的时间内找到最优路径。
三、WAZE算法WAZE算法是一种基于实时交通数据的路径规划算法。
相比于传统的静态算法，WAZE算法能够根据实时交通状况动态调整路径。
它通过收集用户提供的交通速度数据，结合历史交通数据和实时路况信息，预测未来的交通状况并进行路径规划。
WAZE算法的优点是能够提供最实时的路径信息，但需要大量的数据支持，对用户的位置隐私也存在一定的威胁。
四、多标签A*算法多标签A*算法是A*算法的进一步优化，它能够同时考虑多个标签的约束条件。
例如，我们可以通过设置多个标签来要求路径不仅仅是最短的，还需满足其他条件，如最经济的、最环保的或最安全的等。
多标签A*算法通过在搜索中动态更新多个标签的权重，实现了基于多个约束条件的路径规划。
综上所述，导航系统中的路径规划算法有最短路径算法、A*算法、WAZE算法和多标签A*算法等多种。
带权重的最短路径的计算公式带权重的最短路径算法是一种在图中寻找从起点到目标节点最短路径的方法。
不同于普通的最短路径算法，带权重的最短路径算法会考虑每条边的权重，即每条边的长度或代价。
在现实生活中，我们常常需要在地图上找到最短路径，例如从家到公司，或者从学校去旅游景点。
然而，有些路径可能并不是最短的，因为它们可能经过繁忙的街道或者需要支付过高的通行费。
这时，我们就需要使用带权重的最短路径算法，以便找到既短又经济的路径。
带权重的最短路径算法有多种，其中最著名的是迪杰斯特拉（Dijkstra）算法。
该算法的核心思想是通过逐渐扩展路径的方式，更新每个节点的最短路径长度。
具体来说，算法会从起点开始，计算与起点相邻的节点的最短路径长度，并将这些节点标记为“已访问”。
然后，算法会选择一个未访问的节点，通过比较当前节点的最短路径长度和经过当前节点到达目标节点的路径长度，更新目标节点的最短路径长度。
算法会不断重复这个步骤，直到所有节点都被标记为“已访问”或者目标节点的最短路径长度不再变化。
除了迪杰斯特拉算法，还有其他的带权重的最短路径算法，如贝尔曼-福特（Bellman-Ford）算法和A*算法等。
贝尔曼-福特算法是一种基于松弛操作（即通过比较当前路径长度和新路径长度，更新最短路径长度）的算法，可以应用于带有负权边的图。
而A*算法结合了迪杰斯特拉算法和贪婪算法的思想，通过估计从当前节点到目标节点的距离，动态地选择下一个节点，以减少不必要的计算。
带权重的最短路径算法在实际应用中具有广泛的指导意义。
例如，在网络路由中，我们需要找到最短的路径来传输数据，以减少通信的延迟和成本。
在物流领域，希望找到最短的路径来减少运输时间和成本。
此外，在社交网络分析中，我们可以使用带权重的最短路径算法来计算两个人的关系强度，从而推断出他们之间的联系紧密程度。
综上所述，带权重的最短路径算法在求解实际问题中具有重要的应用价值。
通过选择合适的算法，我们可以高效地找到最佳路径，从而在节约时间和成本的同时，实现更好的效果。
配送路径优化的方法引言在物流配送过程中，优化配送路径是提高效率、降低成本的关键之一。
优化配送路径可以减少司机行驶距离、减少配送时间、提高配送准时率。
随着信息技术的发展，配送路径优化的方法也得到了很大的改进和创新。
本文将介绍一些主要的配送路径优化方法，并分析其适用场景和优缺点。
一、传统优化方法1. 最短路径算法最短路径算法是最为经典和常用的优化方法之一。
其中，Dijkstra算法和Floyd-Warshall算法是两种常见的最短路径算法。
这些算法通过计算路网中各个节点之间的最短距离，从而确定最优的路径。
最短路径算法适用于规模较小、配送地点相对固定的场景。
•Dijkstra算法：以起始节点为中心，逐步计算其他节点到达起始节点的最短距离。
•Floyd-Warshall算法：通过动态规划的方式计算任意两个节点之间的最短路径。
2. 车辆路径规划车辆路径规划方法主要是针对多车辆配送问题的优化。
其中，主要包括贪心算法和遗传算法等。
•贪心算法：按照某种优先级，每次选择最优的路径进行配送，直到所有路径都被配送完成。
•遗传算法：通过模拟遗传进化的方式，在候选路径集合中寻找最优解。
二、基于智能算法的优化方法随着信息技术的迅速发展，智能算法逐渐应用于配送路径优化领域，通过学习和优化来提高配送效率。
1. 遗传算法遗传算法是一种模拟自然界遗传和进化规律的优化算法。
在配送路径优化中，遗传算法可以通过不断迭代、交叉和变异，寻找最优的配送路径。
•初始化种群：随机生成多个候选路径。
•适应度评估：计算每个候选路径的适应度，即路径长度。
•选择操作：根据适应度选择一部分候选路径进行进化。
•交叉操作：随机选择两个路径，将它们的部分路径互换，生成新的候选路径。
•变异操作：随机选择一个路径，对其进行变异，生成新的候选路径。
•迭代操作：通过多次迭代，不断优化候选路径，直到找到最优解。
2. 蚁群算法蚁群算法模拟了蚂蚁在寻找食物过程中的行为规律，通过蚁群中蚂蚁之间的信息交流和合作，找到最优的配送路径。
最短航线的判定方法
判定最短航线的方法是使用最短路径算法。
最短路径算法是一种寻找图中连接两个节点间最短距离的算法。
以下是两种常用的最短路径算法：
1. Dijkstra算法：该算法适用于没有负权边的有向图或无向图。
它通过从起始节点开始，逐步更新其他节点的距离，直到找到最短路径为止。
2. Floyd-Warshall算法：该算法适用于有向图或无向图，可以处理边权值为负数的情况。
Floyd-Warshall算法通过一个动态规划的过程，计算所有节点间的最短路径。
在使用最短路径算法判定最短航线时，需要将航线抽象为一个图，节点表示地点，边表示航班，边的权值表示航班的飞行时间或距离。
根据实际情况，选择合适的最短路径算法，并给出起始节点和目标节点，即可计算出最短航线的距离或路径。
机器人导航中的路径规划算法随着人工智能和机器人技术的不断进步，机器人导航已经变得越来越普遍。
机器人导航中的路径规划算法起着至关重要的作用，它能够帮助机器人找到最佳路径来完成给定任务。
本文将讨论机器人导航中常用的路径规划算法及其特点。
一、最短路径算法最短路径算法是机器人导航中最常用的算法之一。
它的目标是找到两点之间的最短路径，使机器人能够以最快的速度到达目的地。
其中，最著名的算法是Dijkstra算法和A*算法。
1. Dijkstra算法Dijkstra算法是一种基于图的搜索算法，它通过计算从起点到终点的最短路径来引导机器人导航。
该算法从起点开始，逐步扩展搜索范围，每次找到当前距离起点最短的节点，并将其加入已经访问过的节点集合中。
同时，更新其他节点的最短距离值，直到找到终点或者搜索完整个图。
Dijkstra算法的优点是保证能够找到最短路径，但计算复杂度较高，适合用于小规模的导航问题。
2. A*算法A*算法是一种启发式搜索算法，结合了广度优先搜索和启发式估计函数的思想。
与Dijkstra算法相比，A*算法通过引入启发式函数来提高搜索效率，从而在更短的时间内找到最短路径。
在A*算法中，每个节点都会被分配一个估计值，与该节点到终点的预计距离相关。
A*算法会优先搜索具有较小估计值的节点，从而尽快找到最短路径。
这种估计函数可以根据具体问题的特点来设计，例如欧氏距离、曼哈顿距离等。
A*算法在大多数情况下比Dijkstra算法更高效，但在某些特殊情况下可能会出现误导机器人的问题。
二、避障路径规划算法除了找到最短路径，机器人导航还需要考虑避障问题。
避障路径规划算法能够帮助机器人避开障碍物，安全到达目的地。
以下是两种常用的避障路径规划算法：1. Voronoi图Voronoi图是一种基于几何空间的路径规划算法。
它通过将已知障碍物的边界等分成小区域，形成一张图。
机器人可以在保持离障碍物最远的同时，选择通过Voronoi图中的空区域进行移动。
求解单源最短路径问题的算法
求解单源最短路径问题的算法有多种，下面列举了几种常见的算法：
1. Dijkstra算法：通过维护一个距离数组，不断更新起始点到其他节点的最短路径长度。
核心思想是每次选择距离起始点最近的节点，并逐步更新距离数组。
该算法适用于无负权边的情况。
2. Bellman-Ford算法：通过迭代更新距离数组，每次都扫描所有的边，更新路径长度。
该算法适用于存在负权边的情况。
3. Floyd-Warshall算法：通过一个二维矩阵来存储任意两个节点之间的最短路径长度，通过尝试经过不同的中间节点来更新路径长度。
该算法适用于有向图或无向图，且适用于任意权重的情况。
4. A*算法：在Dijkstra算法的基础上引入启发函数，通过启发函数估计从起始点到目标节点的距离，并按照估计值进行优先级队列的排序。
该算法适用于图中存在目标节点的情况。
以上算法适用于不同的情况，具体选择哪个算法要根据问题的特点来决定。
利用Dijkstra算法计算最短路径摘要福格环游地球问题是一个十分典型的最短路径求解问题，题设给出了当时世界上主要交通网络图及交通通畅的城市之间来往所需时长，并限定了福格的出行方向（福格选择的是往东走），给出起止地点后要求找出福格环游世界天数最短的最佳路径。
我们认为，这个问题的实质在于最短路径的求解和优化。
我们对比图论中的多种最短路径算法，决定利用Dijkstra算法解决这个问题。
由于Dijkstra算法要求输入图G的关联矩阵，且图G为二维赋权图，而题中给出的地图可看成是三维环状地图，因此，我们对题设地图做相关处理，将其从起点处“切断”并展开为二维图，然后根据此图建立关联矩阵。
同时，我们考虑到最短路径可能会与切断线有交点，在切断线以西找出若干地点一分为二，修改关联矩阵。
对于题目中缺失的两处数据，本文将以当时的交通数据为基础，经过合理的数据处理，结合Google Earth测距软件与题目数据的合理类比，补充缺失数据，完成关联矩阵。
得到关联矩阵后，我们分别以伦敦、纽约和上海作为起点，调整关联矩阵起点和终点，用matlab编程进行求解得到最短环游时间和最短路径，进而判断出所选择的路径是否能让他赢得赌注。
根据我们的求解结果，在这三个城市，福格均能在80天内环游地球，赢得赌注。
本文进一步对此种算法的优缺点、灵敏度与推广性进行了分析，同时初步提出了两种优化方法。
关键词：最短路径算法 dijkstra算法算法优化一、问题重述儒勒•凡尔纳的著名小说《环游世界80天》中，英国绅士福格在伦敦与人打赌能够在80天内环游世界，这在当时的1872年是一个了不起的壮举。
当时最快的旅行方式是火车和轮船，然而世界上大部分地区还是靠马车、大象、驴子或者步行来旅行。
下面是一个从伦敦环游世界不同路线的交通网络图，福格选择的是往东走，每段路线所需要的天数显示在图上（见附录一），旅行的时间基于1872年能采用的旅行方式以及距离。
我们将解决以下问题：1．我们将设计一个算法为福格选择一条最佳路径，即环游世界天数最短，并判断所选择的路径是否能让他赢得赌注。
最短距离算法（Dijkstra） 设计与编程实现 所在系（院）： 专 业： 班 级： 学 号： 姓 名：
绪 论 随着知识经济的到来，信息将成为人类社会财富的源泉，网络技术的飞速发展与广泛应用带动了全社会对信息技术的需求，最短路径问题作为许多领域中选择最有问题的基础，在电子导航，交通旅游，城市规划以及电力、通讯等各种管网、管线的布局设计中占有重要地位。 最短路径，顾名思义就是在所有的路径中找到距离最短的路径，而我们所说的最短路径通常不仅仅指地理意义的距离最短，还可以引申到其他的度量，如时间、费用、路线容量等。相应地，最短路径问题就成为最快路径问题，最低费用问题等，所以我们所说的最短路径也可以看做是最优路径问题。 最短路径问题在交通网络结构的分析，交通运输线路的选择，通讯线路的选择与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接应用的价值。最短路径问题在实际中还应用于汽车导航系统以及各种应急系统等，这些系统一般要求计算出到出事点的最佳线路，在车辆行驶过程中还需要实时的计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效的。 最短路径问题一直是计算机学科，运筹学，交通工程学，地理信息学等学科的一个研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断的涌现。 1 定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）
2 概要设计和数据结构选择
按路径长度递增的顺序产生最短路径。通过以上对问题的分析和任务的理解，设计出一个大体的模块和程序流程。 2.1程序中涉及到的结构体及子函数：
2.1.1结构体： 本程序设计使用了以下结构体： struct vertex { int num; //顶点编号 int data; //顶点信息 }; //顶点类型 typedef struct graph { int n; //图中顶点个数 int e; //图中边的个数 struct vertex vexs[MAXVEX]; //顶点集合 int edges[MAXVEX][MAXVEX]; //边的集合
}AdjMaxix; //图的邻接矩阵类型 2.1.2子函数：
设计本程序需分成几个模块，要用到以下几个子函数： AdjMaxix creatmgraph() //通过用户交互产生一个有向图的邻接矩阵； void dispmgraph(AdjMaxix adj)//用于输出一个有向图的邻接矩阵； void ppath(int path[],int i,int v0)； //选择输出一条最短路径 void DisPath(int dist[],int path[],int s[],int n,int v0) //用path计算最短路径 void Dijkstra(AdjMaxix g,int v0) // Dijkstra算法 void change(int num) //用于替换顶点编号
2.1.3结构图与流程图
结构图如图1
图1 结构图 ppath main
DisPaDijkstchangcreatdispm 流程图如图2
图2 程序流程图 输入语句，cin>>n>>e; cin>>b>>t>>w;
Dijkstra算法 dist[i]=g.edges[v0][i];s[i]=0;if(g.edges[v0][i]
s[v0]=1;path[v0]=0;把源点放入s中；
for(i=0;idist[j]=dist[u]+g.edges[u][j];得出最短路径；
Do{} while(x!='n');
if(i>=n)； if(j>=n)
结束
开始
yes no
yes 3.详细设计和编码 这里设计用邻接矩阵解决实际生活中城市间往返最短路径问题。
3.1算法思想
把图中顶点集合分成两组，第一组为集合S，存放已求出其最短路径的顶点，第二组为尚未确定最短路径的顶点集合是V-S（用U表示），其中V为网中所有顶点集合。在这里我们设计一个有向图G=（V，E）为G地区的交通图。 在这个图中，V=（1，2，……，N）代表各个城市。edges是表示G的邻接矩阵，edges[I][j]表示有向边的权，这里的权值代表城市间距离。若不存在有向边的权，则edges[I][j]的权为无穷大（可取值为INF=32570）。设S为一个集合，其中的每个元素表示一个城市，求出从源点（自定义）城市到这些顶点城市的最短距离。S的初态只包含顶点V0。数组dist记录从V0到其他各城市当前的最短距离，其初值dist[I]=edges[V0][I]。从S之外的顶点集合V-S中选出一个城市u。使dist[w]的值最小。于是从源点到达u只通过S中的城市，把u加入集合S中调整dist中记录的从源点到V-S中每个城市V的距离：从原来的dist[v]和dist[w]+edges[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到S中包含V中其余顶点的最短路径。 3.1.1算法描述 void Dijkstra(AdjMaxix g,int v0) {int dist[MAXVEX],path[MAXVEX]; int s[MAXVEX]; int mindis,i,j,u,n=g.n; for(i=0;i{ dist[i]=g.edges[v0][i]; s[i]=0; if(g.edges[v0][i]path[i]=v0; else path[i]=-1; } s[v0]=1;path[v0]=0; for(i=0;i{ mindis=INF; u=-1; for(j=0;jif(s[j]==0 && dist[j]{ u=j; mindis=dist[j]; } s[u]=1; for(j=0;jif(s[j]==0) if(g.edges[u][j]{ dist[j]=dist[u]+g.edges[u][j]; path[j]=u; }
3.2采用邻接矩阵的存储结构 3.2.1基本概念 图的邻接矩阵可以使用一个二维数组存储顶点之间相邻关系的邻接矩阵，和一个具有N个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点Vi的信息。
3.2.2算法描述 void Creatdl(vexlist GV,adjmatrix GA,int n,int e) { int I,j,k,w; cout<<”输入”
对设计实现的回顾讨论和分析；算法的时、空性能分析和改进设想，经验和体会等。
4.1调试中遇到的问题与解决方法 在进行输入输出语句的调试时，系统提示无法识别函数，缺少头文件; 出现重大错误，多达数百条错误，着实郁闷了一阵；很多标点符号是在中文输入法状态下输入，造成系统无法识别，改掉后错误消失；如 switch语句，在每条选择语句后，缺少break()，错误； 函数方法使用有误，无法通过；在赋实参时，对于变化的实参只需赋初值，子函数也可以调用子函数； 困惑很久的调用子函数问题，在赋实参时找不到实参；用switch语句进行相关选择代换，成功。 连系实际问题上，int型与char型的替换上不知道用什么函数实现；
4.2设计体会
对C语言的使用不是很熟练，造成自己浪费很多时间在复习C语言，如：结构体的使用，不能灵活应用do,while( )，switch( ) 语句等；调用子函数问题上，子函数之间错综复杂的调用和实参，形参的赋值让自己很是迷惑，三天时间，也许更多时间里，都是在研究怎样调用子函数。虽然最后基本是完成了教授布置下来的课程设计，但是还是有不尽人意的地方：结点的插入，删除，路径的实际化最终由于时间问题没能解决，很遗憾。程序缺乏人性化设计，估计第一次使用本程序的人会很迷茫。
4.3时间空间复杂度的计算
利用Dijkstra算法求解最短路径时，求每一对顶点之间的最短路径的一种方法是反复执行n次Dijkstra算法, 每次执行以一个顶点为源点, 求得从该顶点到其它各顶点的最短路径; 其时间复杂度为O(n3)。其空间的复杂度为o(n)。 5.测试结果
输入数据 ： 输入城市数为：4
