迷宫最短路径问题的计算机解法

迷宫最短路径问题的计算机解法（共6篇）

1.迷宫最短路径问题的计算机解法 篇一

网络分析（最短路径问题分析）

一、实验目的：

理解最短路径分析的基本原理，学习利用arcgis软件进行各种类型的最短路径分析的操作。

二、实验准备

1、实验背景：

最短路径分析是空间网络分析中最基本的应用，而交通网络中要素的设置对最短路径的选择有着很大的影响。实验要求根据不同的权重，给出到达指定目的地的路径选择方案，并给出路径长度。

 在网络中指定一个超市，要求分别求出在距离、时间限制上从家到超市的最佳路径。

 给定访问顺序，按要求找出从家经逐个地点达到目的地的最佳路径。

2、实验材料：

软件：ArcGIS Desktop 9.x，实验数据：文件夹ex6中，一个GeoDatabase地理数据库：City.mdb，内含有城市交通网、超市分布图，家庭住址以及网络关系。

三、实验内容及步骤

首先启动ArcMap，选择ex6city.mdb，再双击后选择将整个要素数据集“city”加载进来，然后将“place”点状要素以“HOME”字段属性值进行符号化，1值是家，0值是超市。

第1步 无权重最佳路径的选择  加载 “设施网络分析”工具条（“视图”>>“工具条”，勾选“设施网络分析”），点选旗标和障碍工具板下拉箭头，将旗标放在家和想要去的超市点上。

第2步 加权最佳路径选择

 在设施网络分析工具条上，点选旗标和障碍工具板下拉箭头，将旗标放在家和想去的某个超市点上。

 选择“分析”下拉菜单，选择“选项”按钮，打开“分析选项”对话框，选择“权重”标签页，在“边权重”上，全部选择长度“length”权重属性。 点选“追踪任务”下拉菜单选择“查找路径”。单击“执行”键，则以长度为比重为基础的最短路径将显示出来，这条路径的总成本将显示在状态列。

 上述是通过距离的远近选择而得到的最佳路径，而不同类型的道路由于道路车流量的问题，有时候要选择时间较短的路径，同样可以利用网络分析进行获得最佳路径。

第3步 按要求和顺序逐个对目的点的路径的实现

 在设施网络分析工具条上，点选旗标和障碍工具板下拉箭头，将旗标按照车辆访问的顺序逐个放在点上。

 选择“分析”下拉菜单，选择“选项”按钮，打开“分析选项”对话框，选择“权重”标签页，在“边权重”上，全部选择长度“length”权重属性。 点选“追踪任务”下拉菜单选择“查找路径”。单击“执行”键，则从起点按顺序逐一经过超市最后回到家的最短有效路径将显示出来，这条路径的总成本将显示在状态列。

同样是经过这11个地点，换成权重是时间的，由于道路车流量的不同，如在市中心车流量特别大，车速慢，故而为节约时间，所以使得路径发生很大的改变。

第4步 阻强问题

这里的阻强是指网络中的点状要素或线状要素因为实际中遇到的例如修路，或那个时段车辆饱和，十字路口发生事故等一些缘故而使得要素不可运行，这时原来获得的最短路径就需要进行修正，具体操作如下： 修路的情形出现，即某个路段不可运行，这在网络中的表现是设置阻强，方法有两种，一种是永久性的，直接将网络边要素的属性修改成不可运行。选择要进行设置的边要素，将其属性中的“Enabled”字段改成“False”即可；另一种是暂时性的，设置边要素障碍。即利用边要素障碍添加工具将边设置。



4、心得体会 ：

2.迷宫最短路径问题的计算机解法 篇二

贪婪算法: 又称贪心算法,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择[1]; 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。贪心算法有两个基本要素: 1) 贪心选择性质: 指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。2) 最优子结构性质: 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质[2]。

遗传演化算法是一类借鉴生物界“适者生存,优胜劣汰”遗传机制的进化规律演化而来的随机化搜索方法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象并产生下一代的解[3]; 在每次迭代中都保留一组候选解,逐步淘汰掉适应度函数值低的解,保留适应度函数值高的解。利用遗传算子( 选择、交叉和变异) 对这些个体进行组合,产生新一代的候选解群,重复此过程,直到满足某种收敛指标为止。

1 最短路径问题的描述和数学模型

最短路径问题又被称为旅行商问题、货郎担问题,简称为TSP问题,该问题是在寻求某一个旅行者从起点出发,通过所有给定的路程点之后,最后再回到起点,最后求最短路径。

旅行商问题描述为: 已知n个城市,且已知每相连两个城市之间的距离 ,现要求有一个人必须遍历这n个城市 ,并且要求此人对每个城市只能访问一次 ,且最后必须返回出发城市 。 问如何安排他对这些城市的旅行次序 ,可使其旅行路线的总长度最短[4]?

2 演化算法基本原理和算法描述

2. 1 编码方案

演化算法并不能解决问题空间的数据,我们需要将问题空间的数据转化为遗传空间的数据,称为编码。演化算法有多种编码方式: 二进制编码,浮点数编码,格雷码编码,符号编码,复数编码,矩阵编码,DNA编码等。演化算法使用二值符号集{ 0, 1} 组成这样初始群体中各个个体的基因值用均匀分布的随机数而生成。如: 11100111011就可表示一个个体。由于遗传算法不能直接处理问题空间的数据,所以我们必须将问题空间的数据映射成遗传空间的基因型串结构数据,在求解旅行商问题上,采用顺序编码方法,例如现在要计算武汉、上海、广东、北京这四个城市的一条最优路径,我们给它们编上号,武汉( 0) 、上海( 1) 、广东( 2) 、北京( 3) ,路径( 上海-> 北京-> 武汉-> 广东) 可以表示成基因型串结构数据( 1302) ,即以城市的遍历次序作为遗传算法的编码[5]; 例: A =[6 3 10 1 5 7 4 8 9 2]。

2. 2 计算适应度

个体适应度在演化算法中用来衡量每一个个体可能遗传到下一代种群中的机会比率。它是根据目标函数来进行评估的。 适应度函数的选取直接影响演化算法的收敛速度以及能否找到最优解。采用的适应度函数为个体巡回路径的总长度的函数[6]; 具体为:

式中Adapt( 1,i) 表示第i个个体的适应度函数,maxdis为城市间的最大距离,为4077 km,dis为个体巡回路径的总长度,这样定义的适应度,当路经越短时适应度值越大。在适应度值的基础上,给出的计算个体期望复制数的表达式为其中,sumadapt为种群适应度之和:

2. 3 选择算子

是决定父代种群中哪些个体能被挑选来复制或遗传到下一代的一种仿生进化操作,选择算子以对个体的适应度评价为基础,其主要作用是对搜索提供导向: 挑选最适应度最秀个体,使算法避免无效搜索,并且能快速搜索到问题的最优解。具体操作方法为: 首先计算群体中所有个体适应度的总和 ( ∑f) ,再求出每个个体适应度所占的比例( fi/ ∑f ) ; 则算出选择概率Pi = ( fi / ∑f) ,根据轮盘选择法算出每个个体被选择的概率, 利用向量prob存储选择概率之和,向量ms存储归一化的随机数,经过比较prob和ms中的元素,选择出下一代的个体。

2. 4 交叉算子

交叉算子是模仿生物有性繁殖,通过两个母体交叉,产生出交配后的子代,子代的基因值不同于父代。交换是演化算法产生新个体的主要手段。常用的交叉算子有单点交叉,多点交叉, 均匀交叉。若采用单点交叉,则产生非法路径。本实例中交叉采用部分匹配交叉策略,其基本实现的步骤是:

步骤1随机选取两个交叉点( 带箭头的位置) 。

步骤2将两交叉点中间的基因段互换。如 ( 45671和14032) 。

步骤3将互换的基因段以外的部分,若这部分的元素与互换后基因段中元素冲突的,就用另一父代的相应位置代替,直到没有冲突,如图1所示。

2. 5 变异算子

变异的目的就是改善演化算法的局部搜索能力,维持群体的多样性,防止出现早熟现象。具体做法是: 若个体是由二进制编码符号串所表示,将某一基因座上的原有基因值为0,则变异操作将该基因值变为1,反之,若原有基因值为1,则变异操作将其变为0; 如图2所示,将个体8345671902中的两个基因3和9互换后得到新个体8945671302。

为了收敛 到最优解,借鉴模拟退火算法的思想,采取了变异率由很大逐渐衰减到较小的数量,这样做也利于找到全局最优解。

2. 6 演化算法的程序流程

Step1首先选择目标函数,然后确定算法的编码方案;

Step2随机产生一个规模为M大小的种群,判定种群中每个个体是否满足算法的终止条件;

Step3计算每个个体的适应度,根据适应度对优良个体进行选择操作;

Step4对被选择的个体进行交叉操作,形成新种群;

Step5选择个体进行变异操作形成新种群;

Step6判断是否满足终止条件 ,若满足则退出,否则转到Step3。

3 算法改进: 贪婪算法优化种群

针对传统的演化算法进行改进,使用贪心算法优化初始种群,基本遗传算法通过随机方法产生初始种群,生成的初始种群质量不高,严重制约算法的收敛速度。

对问题求解时,贪心算法总是做出在当前看来是最好的选择,也就是说,不从整体最优上加以考虑,它所做出的仅是某种意义上的局部最优解。假定m个城市的最短路径问题,设定种群规模为M。本算法利用贪婪算法优化初始种群的基本思想是: 先从m个城市中选一个作为起点城市,假设为1。从余下 ( m - 1) 个城市中找距离1最近的城市,假设为5,并且在距离信息中作出标记,标出1 - 5已使用。再从5找距离5最短并且没有在已生成个体中出现的城市: 即在已生成个体中之外城市。 依此类推,生成下一个个体时,首先从没有走过的路径中选择最短的,直到遍历m个城市得到初始个体,由此产生0. 2 m个初始个体,然后再随机产生0. 8 m个初始个体,从而得到规模为M的初始种群。

根据贪心算法生成的这部分初始种群具有很多特点: 如定义长度短,适应度高等。这部分种群的加入提高了初始种群的整体质量,并且也不会影响初始种群多样性。贪婪算法优化后的初始种群,克服了有传统演化算法初始种群适应度低的缺点, 高质量的初始种群有助于缩短求得最优解的时间,同时求得更优的最短路径。

4 仿真实验和结果

在主频为2 . 40 GHz的PC机器上,采用Matlab 7. 0软件仿真国际标准数据库TSPLIB中的算例,所给中国31城市相对坐标见文献[7]。其中算法参数为: 群体规模: N = 500; 最大迭代代数: M = 500,交叉概率PC = 0. 8,变异概率PM = 0. 05 。 本文算法仿真效果如图3所示。

以上是本文改进演化算法求得的31个城市最短路径仿真实验效果图,将本文算法分别和简单演化算法 ( SGA ) ,文献 [7]中的改进演化算法,文献[8]中的改进演化算法进行比较, 得出的实验结果性能表,如表1所示。

由表1可知,在种群数设置和最大迭代数设置相同情况下, SGA算法求得最短路径为17 204,文献[7]的算法求得最短距离为16 309,文献[8]的算法求得最短距离为15 387,而本文提出的改进的演化算法GGA求得最短距离为15 377,很显然GGA求得的结果优于其他算法。

5 结 语

3.迷宫最短路径问题的计算机解法 篇三

关键词：最短；假设；转化；平移；对称

中图分类号：G633.6 文献标识码： A 文章编号：1992-7711（2016）18-059-02

0

众所周知，转化思想是数学中最基本的数学思想。而假设法也是一种重要的数学思维方法，在问题的转化过程中，假设起“桥梁”作用。下面我们以数学人教版八年级“课题学习——最短路径问题”为例，来体验一下假设法对于问题转化的重要性。

一、模型1——在直线上求作一点与直线同侧的两点所连线段之和最小

例1：如图1-1，点A，B分别是直线异侧的两个点，在上求作一点C，使CA+CB最短。

解决策略：连接AB，与直线的交点即为所求。

这是最基本的数学模型。下面我们用假设法对这个模型进行举一反三、拓展应用。

二、模型1“变形记”——模型2

模型2：在直线上求作一点与直线异侧的两点所连线段之和最小

例2：如图2-1，点A，B分别是直线同侧的两个点，在上求作一点C，使CA+CB最短。

如图2-2，假设把河面看作一面镜子，点B反射到另一侧点B'处，则A、B'两点位于直线异侧，“模型2”就转化为“模型1”。当然，作点A的对称点也可。

解决策略：先作其中一个点关于这条直线的对称点，再连接对称点与另一个点，与该直线的交点即为所求。要证CA+CB最短，如图2-3，在直线上另外任取一点C'，然后证明AC+BC三、模型1再“变身”

提到“河”，人们会想到“桥”。下面就来谈谈人们熟悉的造桥选址问题。

例3：如图3-1，从A地到B地经过一条小河（河岸a∥b），现要在河上建一座与两岸垂直的桥MN，桥造在何处才能使从A地到B地的路径AMNB最短？

分析：造的桥要与河垂直，由于路径AMNB中的MN的长度是个定值（等于河宽），因此只需使AM+NB最小即可。

（一）法1——条件假设，变“因”导“果”

在本例中，假如河的宽度变为零，这个问题就转化成前面所讲的“模型1”。

如图3-2，将点A向与河岸垂直的方向平移一个河岸宽度到A1，我们可以假想直线a也平移到了直线b并与a重合，由于点A1和点B分别位居直线b两侧，由“模型1”可知，只需连接A1B，交河岸于点N，在此处造桥MN，所得路径AMNB就是最短路径。

略证：如图3-3，如果在不同于MN的位置造桥M1N1.由于M1N1=MN=AA1；又根据“两点之间，线段最短”，AN1+N1B>A1N+NB，故路径AMNB要短于AM1N1B.

（二）法2——结论假设，执“果”索“因”

如图3-2，从A到B可行走的路线是A→M→N→B，假设在此路线中AM+BN最短，现来找一找它应该满足的条件.要使AM+BN最短，需将两线段拼在一条直线。因为两点之间，线段最短，故将AM平移到A1N，使A1、N、B三点共线，A1N+NB最小.此时，AM∥A1N且AM=A1N，可证四边形AMNA1是平行四边形，则AA1=MN；因此，需要先将点A向垂直于直线b的方向平移一个河岸宽度到A1处。

四、模型1拓展记

（一）情景设疑

如果一条河变成两条河，需要驾两座桥或更多座桥，又该如何选址呢？

例4：如图4-1，从A地到B地经过两条小河，现要在河上建两座与河岸垂直的桥，则在何处建桥才能使从A地到B地的路径最短？

（二）解法展示

法1：将其中的点A或点B连续平移两次

如图4-2，先将点A沿与河流河岸垂直的方向平移一个河宽到A1，再沿与河流2河岸垂直的方向平移一河宽到A2，连接A2B，交河流2河岸于N，此处建桥MN；连接A1M，交河流1于P，在此处建桥PQ，所得路径AQPMNB最短。

法2：将点A、点B分别平移一次

如图4-3，将A沿与河流1垂直的方向平移一个河宽，得到A1，再将B沿与河流2河岸垂直的方向平移1个河的宽度得到B1，连接A1B1与河流1、河流2分别相交于N、P，分别作桥MN、PQ，所得路径AQPNMB最短。

（三）归纳小结

由上可知，造桥选址问题，要使所得到的路径最短，通过平移变换（向垂直于河岸的方向平移），使除了桥长不变外所得到的其他路径平移后在一条直线上。

五、模型1、模型2“融合記”

分析：本例是平移变换和轴对称变换的综合题，同样也可以用假设法解决。如图5-2，假设PQ的长度为零，将点B沿平行于直线的方向朝左平移PQ的长（定长）至B'，再在直线上找一点P，使AP+PB'最小（转化为模型2），最后作点A关于直线的对称点A'（转化为模型1），连接A'B'，交直线于P；最后在直线上截取线段PQ等于定长。则此时AP+PQ+BQ最小，原理如图5-3所示（证明略）。

综上所述，在解决最短路径问题时，我们可以用假设法，利用轴对称、平移等变换把不在一条直线上的几条线段转化到一条直线上，从而得出最短路径。这样将未解决的问题转化为另一个较易解决的问题或已经解决的问题，真正实现了化难为易，化未知为已知，从而迅速找到问题的突破口，提高解题能力。

[参考文献]

[1]义务教育数学课程标准.2011年版.北京师范大学出版社，2012.01.

4.迷宫最短路径问题的计算机解法 篇四

// _DataStructure_C_Impl:Dijkstra#include#include#includetypedef char VertexType[4];typedef char InfoPtr;typedef int VRType;#define INFINITY 100000 //定义一个无限大的值#define MaxSize 50 //最大顶点个数typedef int PathMatrix[MaxSize][MaxSize]; //定义一个保存最短路径的二维数组typedef int ShortPathLength[MaxSize]; //定义一个保存从顶点v0到顶点v的最短距离的数组typedef enum{DG,DN,UG,UN}GraphKind;typedef struct{ VRType adj; //对于无权图，用1表示相邻，0表示不相邻；对于带权图，存储权值 InfoPtr *info; //与弧或边的相关信息}ArcNode,AdjMatrix[MaxSize][MaxSize];//图的类型定义typedef struct{ VertexType vex[MaxSize]; //用于存储顶点 AdjMatrix arc; //邻接矩阵，存储边或弧的信息 int vexnum,arcnum; //顶点数和边（弧）的数目 GraphKind kind; //图的类型}MGraph;//添加一个存储网的行、列和权值的类型定义typedef struct{ int row; int col; int weight;}GNode;//采用邻接矩阵表示法创建有向网Nvoid CreateGraph(MGraph *N,GNode *value,int vnum,int arcnum,VertexType *ch){ int i,j,k,w; char s[MaxSize]; VertexType v1,v2; N->vexnum=vnum; N->arcnum=arcnum; for(i=0;ivex[i],ch[i]); //初始化邻接矩阵 for(i=0;ivexnum;i++) for(j=0;jvexnum;j++){ N->arc[i][j].adj=INFINITY; N->arc[i][j].info=NULL; //弧的信息初始化为空 } for(k=0;karc[i][j].adj=value[k].weight; } N->kind=DN; //图的类型为有向网}//输出邻接矩阵存储表示的图Nvoid DisplayGraph(MGraph N){ int i,j; printf(有向网具有%d个顶点%d条弧，顶点依次是: ,N.vexnum,N.arcnum); for(i=0;i

5.利用轴对称变换求最短路径问题 篇五

解法:作点B关于直线l的对称点B′, 连结AB′, 与直线l相交于点P, 连结BP。骑马少年沿折线A-P-B的路线行走时路程最短。

证明:如图, 在直线l上任取一点P′ (与点P不重合) , 连结AP′, BP′, B′P′.

由轴对称的性质知, BP=B′P, BP′=B′P′

∴AP+BP=AP+B′P=AB′, AP′+BP′=AP′+B′P′

在△AB′P′中, AB′<AP′+B′P′

∴AP+BP<AP′+BP′。

即AP+BP最短。

“最短路径问题”的原型就来自于“饮马问题”, 要解决这一问题, 是利用作对称点把折线问题转化成直线问题, 它离不开构建与转化“两点之间, 线段最短”的数学公理。在日常生活、工作中, 也经常会遇到有关行程路线的问题, 我们把这类求近道的问题统称最短线路问题, 出题者通常以直线、角、三角形、特殊四边形、坐标轴等对称图形为背景。本文就在“最短路径”中探寻一番, 举例分析, 帮助同学们学习。

【迁移与拓展】

1.一点两线 (相交) 解决周长最短。

如图所示, 点P为一处马厩, ON为草原的边缘 (下方为草原) , OM为一条河流。清晨, 骑马少年要从马厩牵马先去草地吃草, 然后到河边饮水, 最后再回到马厩。请帮他设计一条最近的行走路线。

解析:依据两点之间线段最短, 可分别作点P关于OM, ON的对称点分别为P1、P2, 连P1P2交OM、ON于点A、B。此时ΔPAB的周长PA+PB+AB=P1P2为最小。 (证明略)

2.二点两线 (相交) 解决周长最短。

如图所示, P为帐篷, Q为马厩, 骑马少年某天要从马厩牵出马, 先到草地边ON的某一处牧马, 再到河边OM饮水, 然后回到帐篷, 请你帮他确定这一天的最短路线。

解析:如图分别作点P、Q关于OM, ON的对称点为P′、Q′, 连P′Q′, 交OM、ON于点A、B。此时四边形PABQ的周长PA+AB+BQ+PQ=P′Q′为最小。 (证明略)

3.一点两线 (相交) 解决距离之和最短。

如图所示, A为马厩, 骑马少年某天要从马厩牵出马, 先到河边OM的某处P饮水, 再到草地ON边某处B牧马, 请你帮他设计一条路线, 使AP+BP最短。

解析:如图作点A关于OM的对称点A′, 过A′作ON的垂线交OM于P, 交ON于B, 则A→P→B为最短路线。 (证明略)

【应用与延伸】

1.如图, 一次函数y=kx+b的图象与x、y轴分别交于点A (2, 0) , B (0, 4) , ?O为坐标原点, 设OA、AB的中点分别为C、D, P为OB上一动点, 求PC+PD的最小值, 并求取得最小值时P点坐标。

解析:作点C关于y轴的对称点C', 连接C'D, 交y轴于点P则C'D=C'P+PD=PC+PD。C'D就是PC+PD的最小值, 连接CD, 则CD=2, CC'=2。在直角△C'CD中, 根据勾股定理C'D=2求直线C'D的解析式, 由C' (-1, 0) , D (1, 2) 得y=x+1当x=0时, y=1, 则P (0, 1) 。

2.如图, 已知直角梯形ABCD中, AD∥BC, AB⊥BC, AD=2, BC=DC=5, 点P在BC上移动, 则当PA+PD取最小值时, △APD中边AP上的高为_____。

3.如图, 已知⊙O的直径CD为4, ∠AOD的度数为60°, 点B是弧AD的中点, 在直径CD上找一点P, 使BP+AP的值最小, 并求这个最小值。

解析:作点B关于AD的对称点B', 过点B'作B'E⊥AB于点E, 交AD于点F, 则线段B'E的长就是BM+MN的最小值在等腰Rt△AEB'中, 根据勾股定理得到:B'E=4。

6.最短路径的教学 篇六

《数据结构》课程是计算机类信息类专业的基础核心课程, 这门课程掌握的程度影响到其它后续课程的学习, 相关知识也会应用在实际的软件开发中。大多数院校在低年级开设这门课程, 低年级的学生一般只学过一门高级程序设计语言, 如C语言, 对面向对象程序设计、面向对象编程思想、抽象类型、数学模型、解决实际问题的算法了解甚少。笔者长期从事《数据结构》课程的教学, 对这门课程的教学有一套自己的方法。本文以最短路径的教学为例, 论述了《数据结构》中抽象类型--图的教学思路。

1. 问题的提出

随着生活水平的提高, 汽车已经进入千家万户, 工薪阶层拥有汽车已经成为可能。假期上班族开着自己的汽车到外地旅游已经成为一种时尚。在旅游的过程中, 如何缩短路程减少费用, 成了人们关心的问题。如, 旅客要自己开车从福州到乌鲁木齐, 怎样选择线路, 才能使路径的总和最短, 从而费用总和最少。

2. 数学模型

在上面的问题中, 可以把城市看成顶点, 城市之间若有路可到达的话, 在城市对应的顶点之间加上一条边, 在边上加上权值表示两个城市之间的距离, 这样可以构成一个图 (我们称为无向网络) 。在构造无向网络的过程中, 只要考虑感兴趣的城市 (也就是说只要把感兴趣城市对应的顶点加入到无向网络中) , 同样道理, 也只要把感兴趣的线路加入到无向网络中。

3. 存储结构

G.kind存储的值有四种DG, DN, UDG, UDN。DG表示有向图, DN表示有向网络, UDG表示无向图, UDN表示无向网络。G.vertexnum存储的值表示顶点的个数 (或者说是城市的个数) 。G.edgenum存储的值表示边的条数 (或者说是线路的条数) 。G.edges[j][k]存储的值表示两个城市之间的距离。G.vertexs[i]存储的值是城市的名称。

最终, D[j][k]存放从第j个顶点到第k个顶点的最短距离, P[j][k][t]存放从第j个顶点到第k个顶点的最短路径上的顶点的下标, N[j][k]存放从第j个顶点到第k个顶点的最短路径上的顶点的个数。

4. 实现算法

5. 问题的解决

调试过程如下 (带下划线的字符为从键盘输入的数据) :

要创建图, 请输入图的类型,

0表示有向图 (DG) , 1表示有向网络 (DN) , 2表示无向图 (UDG) , 3表示无向网络 (UDN) :3

要创建无向网络 (UDN) , 请输入顶点的数目:25

要创建无向网络 (UDN) , 请输入边的数目:30

要创建无向网络 (UDN) , 请输入25个顶点:

福州南昌上海徐州天津大连沈阳长春哈尔滨北京郑州武汉株州广州深圳南宁柳州贵阳昆明成都西安呼和浩特兰州西宁乌鲁木齐 (回车)

要创建无向网络 (UDN) , 请输入25*25的矩阵, 有边用权值, 无边用0:

请输入起点城市:

请输入终点城市:

从福州到乌鲁木齐的最短路径为:福州---南昌---株州---武汉---郑州---西安---兰州---乌鲁木齐 (5011)

继续吗?请输入 (Y或y表示继续, N或n表示终止) :

请输入起点城市:

请输入终点城市:

从南宁到乌鲁木齐的最短路径为:南宁---柳州---株州---武汉---郑州---西安---兰州---乌鲁木齐 (4949)

继续吗?请输入 (Y或y表示继续, N或n表示终止) :

摘要：本文论述了《数据结构》图论部分最短路径这一小节教学过程当中的一些体会。从实际问题出发, 提出相关的数学模型, 建立相应的存储结构, 在建立的结构上编写算法, 从而达到解决实际问题。

关键词：数据结构,抽象类型,最短路径,教学方法

参考文献

[1]《数据结构 (C语言版) 》, 严蔚敏吴伟民编著, 清华大学出版社, 1997.4