第一篇：最短路径教案
13.4最短路径问题
一、教学内容：本节课的主要内容是利用轴对称研究某些最短路径问题，最短路径问题在现实生活中经常遇到，初中阶段，主要以“两点之间，线段最短”“连接直线外一点与直线上各点的所有连线中，垂线段最短”为知识基础，有时还要借助轴对称、平移、旋转等变换进行研究。
本节课以数学史中的一个经典故事----“将军饮马问题”为载体开展对“最短路径问题”的课题研究，让学生经历将实际问题抽象为数学的线段和最小问题，再利用轴对称将线段和最小问题转化为“两点之间、线段最短”的问题。
二、教学目标
1、能利用轴对称解决简单的最短路径问题
2、再谈岁最短路径的过程中，体会“轴对称”的桥梁作用，感悟转化的数学思想。
三、教学重难点
重点：利用轴对称将最短路径问题转化为“两点之间、线段最短”问题。难点：如何利用轴对称将最短路径问题转化为线段和最小问题。
四、教学问题诊断
最短路径问题从本质上说是最值问题，作为初中学生，在此前很少涉及最值问题，解决这方面问题的数学经验尚显不足，特别是面对具有实际背景的最值问题，更会感到陌生，无从下手。
解答“当点AB在直线l的同侧时，如何在l上找到点C，使AC与BC的和最小”，需要将其转化为“直线l异侧的两点，与直线l上的点的线段的和最小”的问题，为什么需要这样转化，怎样通过轴对称实现转化，一些学生会存在理解上和操作上的困难。
在证明“最短”时，需要在直线上任取一点（与所求做的点不重合），证明所连线段和大于所求作的线段和，这种思路和方法，一些学生想不到。
教学时，教师可以让学生首先思考“直线l异侧的两点，与直线l上的点的和最小”为学生搭建“脚手架”，在证明最短时，教师要适时点拨学生，让学生体会任意的作用。
五、教学过程
教师引语：现实生活中经常会有这样的生活经历，比如学校虽然为我们铺设了一些石板甬路，方便同学们的行走，但是很多时候我们却并不在这些小路上行走，这样做的目的是什么呢？（学生一起回答）如果用数学知识来解释这种行为，那就是我们曾经学习的“两点之间、线段最短”或“垂线段最短”，我们称这样的问题为最短路径问题（板书课题）现实生活中经常涉及到最短路径问题，这节课我们学习的主要任务就是最短路径问题，并用所学知识探究数学史上著名的“将军饮马问题”。
1、情境引入
相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦，有一天，有一位将军专门拜访海伦，求教一个百思不得其解的问题：从图中的A地出发，到一条笔直的河边饮马，然后到B地，到河边什么地方饮马，可使他所走的路线全程最短？精通数学、物理学的海伦稍加思索，利用轴对称的知识回答了这个问题。这个问题后来被称为“将军饮马问题”。
2、探究解决问题的方法
问题一：这是一个实际问题，我们首先把它抽象为数学问题，请同学们用自己的语言说明这个问题的意思。
师生活动：学生独立思考后小组交换意见，然后尝试回答，相互补充，最后达成共识，教师根据学生的回答写出问题的板书：如图，已知点A和点B在直线L的同侧，在直线L上找一点C，使AC与BC的和最小。
设计意图：让学生将实际问题抽象为数学问题，即将最短路径问题抽象为“线段和最小问题”。
问题二：由上面的问题我们可以联想到下面的问题：A、B分别是直线L异侧的两点，如何在直线L上找到一点C，使AC与BC的和最小？
师生活动：学生独立思考，画图分析并尝试回答，教师补充。
问题三：对于第一个问题，如何将点B移到L的另一侧，B′处，满足直线L上的任一点C，都保持CB与CB′的长度相等？ 问题四：你能利用轴对称的知识找到符合条件的点B′吗？
师生活动：学生独立考，尝试画图，然后小组交流，学生代表汇报交流成果，师生共同补充：只要作出点B关于直线L的对称点B′，就可以满足CB=CB′,再利用问题二中的方法，连接AB′,则AB′与直线L的交点即为所求。
学生叙述，教师板书并画图，同时学生在练习本上画图。
设计意图：通过搭建台阶，为学生探究问题提供“脚手架”将同侧难以解决的问题提转化为异侧容易解决的问题，渗透转化思想。
3、推理证明“最短”
问题五：你能用所学的知识证明AC+BC最短吗？
师生活动：师生共同分析，然后学生说证明过程，教师板书。
证明：在直线L上任取一点C′（与点C不重合），连接AC′,BC′,B′C′.由轴对称的性质可知，BC=B′C,BC′=B′C′.∴AC+BC=AC+ B′C=AB′, AC′+ BC′= AC′+ B′C′
在△AB′C′中，AB′＜AC′+ B′C′
∴AC+BC＜ AC′+ BC′ 即AC+BC最短。
问题六：这里任取一点C′的作用是什么？
师生活动：学生相互交流，教师适时点拨，最后达成共识：若直线L上任取一点C′与A、B两点的距离之和都大于AC+BC，则说明AC+BC最短。
设计意图：让学生进一步体会做法的正确性，提高逻辑思维能力。
问题七：回顾前面的探究过程，我们是通过怎样的过程、借助什么解决问题的？
师生共同总结：首先作其中一点关于直线的对称点，然后连接另一点与对称点之间的线段，通过轴对称将两条线段和转化到同一条线段上去，这条线段与直线的交点即为所求，整个过程利用了“轴对称”和“两点之间、线段最短“的知识。
设计意图：让学生在反思的过程中，体会轴对称的“桥梁”作用，感悟转化思想，丰富数学活动经验。
4、巩固练习
（1）如图，一艘旅游船从大桥AB的P处前往山脚下的Q处接游客，然后将游客送往河岸BC上，再回到P处，请画出旅游船的最短路径。
师生活动：学生分析解题思路，并相互补充，然后独立完成画图，学生代表上台讲解。基本思路分析：此题中轮船的行走路线共有三段，其中PQ是必经路段，由“两点之间，线段最短”需首先连接PQ，再将河岸BC看成一条直线，这样问题就转化为“点P、Q在直线BC同侧，如何在BC上找一点R，使PR+QR最小”。
设计意图：让学生进一步巩固解决最短路径问题的基本策略和基本方法。
（2）如图，∠XOY内有一点P，在射线OX上找出一点M，在射线OY上找出一点N，使PM+MN+NP最短．
分析：此题的出题背景就是角。本题主要利用了两点之间线段最短的性质通过轴对称图形的性质确定三角形的另两点．
分别以直线OX、OY为对称轴，作点P的对应点P1与P2，连接P1P2交OX于M，交OY于N，则PM+MN+NP最短．
5、课堂小结：教师与学生一起回顾本节课所学主要内容，并请学生回答：（1）本节课研究问题的基本过程是什么？（2）轴对称在所研究的问题中起到什么作用？
6、布置作业：《课时练》第49页1、2、3、4、5、7、8、9
第二篇：最短路径教案
最短路径问题
教学目标：
1.理解并掌握平面内一条直线同侧两个点到直线上的某一点距离之和为最小值时点的位置的确定。
2.能利用轴对称平移解决实际问题中路径最短的问题。
3.通过独立思考，合作探究，培养学生运用数学知识解决实际问题的基本能力，感受学习成功的快乐。
教学重点：
将实际问题转化成数学问题，运用轴对称平移解决生活中路径最短的问题，确定出最短路径的方法。
教学难点：
探索发现“最短路径”的方案，确定最短路径的作图及原理。
导学过程：
一、创设情景，引入新知。
前面我们研究过一些关于“两点的所有连线中，线段最短”、“连接直线外一点与直线上各点的所有线段中，垂线段最短”等的问题，我们称它们为最短路径问题．现实生活中经常涉及到选择最短路径的问题，本节将利用数学知识探究实际生活中的最短路径问题。
二、自主学习，探究新知。
问题1（将军饮马问题）
牧马人从A地出发，到一条笔直的河边L饮马，然后到B地，牧马人到河边什么地方饮马，可使所走的路径最短？
2、探索问题：
教师提出问题，引导学生思考：
（1）如何将这个实际问题转化为数学问题？转化的要点是什么？
（2）回忆以前学过的“最短”的知识点，（两点之间，线段最短；垂线段最短），思考：这个问题中的“最短”和以前学过的知识有什么相同点和不同点？（3）、如何把“不同点”化为“相同点”？（4）、如何用图形将问题展现出来？
【学生活动】：学生独立思考，画图分析，并尝试回答，相互补充，师生共同归纳：（1）、将A、B两地抽象为两个点，将河L抽象为一条直线（如图2），则问题转化为：如何在L上找一点C，使AC与BC的和最小（如图3）。转化时要注意条件和结论的转化，以及点、线的抽象。
（2）、相同点：都是两点间的最短距离问题。
不同点：一个是两点在L的同侧；一个是两点在L的异侧，并画图比较（如图4）。（3）利用轴对称的知识找出B点关于直线L的对称点B′,就可以满足C B′= CB,再连接A B′，则A B′与直线L的交点C极为所求。
【教师板书并画图】（如图5）
第一步：作出B点关于直线L的对称点B′
第二步：连接A B′，与直线L的交点为C,则C点即为所求。
证明：略
问题二（造桥选址问题）如图,A和B两地在一条河的两岸,现要在河上造一座桥MN.桥造在何处可使从A到B的路径AMNB最短?（假定河的两岸是平行的直线,桥要与河垂直.)
将实际问题中A，B两地与笔直的河L抽象成 点A.点B和直线a，b.如图：
分析：AM+NB最短，要先确定点N在直线b的位置，如果我先将A点往直线a的垂直方向平移MN个单位 后到A′，由于MN垂直直线a，N点就是M点往直线 b的垂直方向平移MN个单位后到的点，由图形平移后 的对应点之间的线段是平行且相等的，得到AM=A′N.AM+NB最短即A′N+NB最短.转变成了直线b上是找 到一点N，使A′ N+NB最短,连结A′,B,与直线b相交的 一点为N点.证明略.三、巩固练习：
1.∠WXZ内有一点Z，在WZ，ZY上分别有点A，B,当△ABZ的周长最小时，请在图中作出点A，B的位置.2.如图，A、B两地之间有两条河，现要在两条河上各造一座桥MN和PQ.桥分别建在何处才能使从A到B的路径最短？（假定河的两岸是平行的直线，桥要与河岸垂直）
四、课堂小结
1、本节主要知识点：
轴对称的对称知识和两点间的最短距离在“最短路径”这类问题中的运用。实际问题与数学问题的转化。
2、提出问题： 这节课你们学到了什么？还有哪些疑惑？
五、布置作业
新观察
第三篇：《最短路径》教学反思
11月23号下午第三节，我讲了公开课《最短路径》第一课时，学校领导及没课的老师来到报告厅听课，听课后田校长对我讲的这一节课经行了点评，我受益匪浅，所以把感悟以及所学到的总结如下：
1、问题设计要有启发性。在设计问题的时候不可以设计无用的问题，要让学生真正有所思考，并且可以经过思考可以得到结论，在设计问题的时候也不要设计太难的问题，打击学生的积极性，要把难的问题分解，解剖成简单的小问题一步步来解决。
2、课堂引入，要更加的正规，不能太随意。比如在引入的时候可以用蚂蚁找食物的实例引入，可以更形象。
3、引入之后，要复习预备知识。因为所有的知识都是在旧知识的基础上生成的，如果说新知识是冰川露出大海的部分，那旧知识就是藏在大海中的更大的部分，所以要强调从旧知识的基础上生成新知识，调动旧知识环境，衍生新知识，这样有利于学生形成数学体系，所学的内容也不会让学生感觉太突兀，而是自然而然的得到。所以要认真分析预备知识，把新知识放在旧知识的基础上，通过复习慢慢引出新的内容，这样学生更容易掌握，更容易接受，不会产生畏难情绪，反而觉得清松自如。
4、授课的过程中应该环环相扣，一步步上，要讲问题分解，化大为小，化难为易，化繁为简，降低难度，就像是上台阶，一个个的台阶上。
5、注重建模思想。虽然不必要提出来这个名词，但是要让学生能从实际问题中抽象出数学问题，本节课的“将军饮马问题”就是一个实际的问题，要让学生转换成数学问题，抽象出数学问题。
第四篇：最短路径_数据结构课程设计报告
数据结构课程设计
《数据结构》课程设计报告
设计题目：____医院选址____________ 姓名：__________________ 学号：________________ 专业：___________
院系：____________
班级：_________________ 指导教师：_________________
年 1月 3 日
数据结构课程设计
一、问题描述
(1)题目内容：有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总和来说较短。（n>=5）(2)基本要求：
(3)可以输出每一对点间的路径长度；然后选取偏心度，最小的偏心度即为所求。
二、需求分析
(4)本程序的功能包括找出每一对点间的路径长度。(5)然后算出每一对点的偏心度。(6)其中最小的偏心度即为所求。
三、概要设计
操作集合：
(7)public:MGraph(DataType a[],int b[][MaxSize],int n,int e);//初始化邻接矩阵和路径
(8)void Floyd();//弗洛伊德算法的实现(9)void getE();//获取偏心度
(10)void showdist();//把每一对顶点之间的路径权值show出来(11)~MGraph(){} //类的析构函数
四、数据结构设计
(1)DataType vertex[MaxSize];//存放图中顶点的数组(2)int
arc[MaxSize][MaxSize];//存放图中边的数组
(3)string path[MaxSize][MaxSize];//存放从Vi到Vj的最短路径，初始为
//path[i][j]=“ViVj”
(4)int dist[MaxSize][MaxSize];//存放求得的最短路径长度(5)int vertexNum, arcNum;//图的顶点数和边数(6)int E[MaxSize][2];//获取最小偏心度和该顶点
五、算法设计
1.算法分析
1）对带权有向图的，调用Floyd算法，对每一对顶点间的最短路径长度的矩阵；
2）对最短路径长度矩阵的每列求最大值，即得到各点的偏心度； 3)具有最小偏心度的顶点即为所求。
数据结构课程设计
数据结构课程设计
2.算法实现
#include
const int MaxSize = 5;template
};template
} template
MGraph(DataType a[], int b[][MaxSize],int n,int e);//构造函数
void Floyd();void getE();void showdist();~MGraph(){} DataType vertex[MaxSize];int arc[MaxSize][MaxSize];int dist[MaxSize][MaxSize];int vertexNum, arcNum;int E[MaxSize][2];
//存放图中顶点的数组 //存放图中边的数组 //存放求得的最短路径长度 //图的顶点数和边数 private:
string path[MaxSize][MaxSize];//存放从Vi到Vj的最短路径，初始为path[i][j]=“ViVj” vertexNum = n;arcNum = e;for(int i=0;i } arc[i][j]=b[i][j];dist[i][j]=arc[i][j]; //直接放入邻接矩阵 for(int j=0;j 数据结构课程设计 } for(i=0;i } for(k=0;k for(i=0;i } //顶点i和j之间是否经过顶点k for(j=0;j } dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=path[i][k]+path[k][j];for(j=0;j } dist[i][j]=arc[i][j];if(dist[i][j]!=10000)else path[i][j]=“";path[i][j]=vertex[i]+vertex[j]; template } template 心度。 } for(int i=0;i } for(int i=0;i } for(int j=0;j “;for(int i=0;i E[i][0]=i;//存放某一个节点的序号 E[i][1]=0;//存放节点的最短路径，权值。 int max = dist[0][i];//i表示列；j表示行。for(int j=0;j if(dist[j][i]>max){ } E[i][1]=max;max = dist[j][i]; 数据结构课程设计 cout< } void main(){ 代表是无穷。 } MGraph 0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};char a[5] = {'A','B','C','D','E'};int b[5][5] = { //邻接矩阵,A,B,C,D,E是节点的信息，代表某一个地点。 //存储某两个有向节点间的权值，代表路径长度，10000 int min=E[0][1],k;for(int i=0;i } cout<<”最佳选址为“< cout< if(E[i][1] } min=E[i][1];k=i; 六、程序测试与实现 1、函数之间的调用关系 Main Floyd() showdist() getE() 2、主程序 void main(){ char a[5] = {'A','B','C','D','E'}; //邻接矩阵,A,B...是节点的信息，代表某一个地点。 数据结构课程设计 int b[5][5] = { //存储某两个有向节点间的权值，代表路径长度，10000代表是无穷。 0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,}; MGraph } GM.Floyd(); GM.showdist(); cout< GM.getE(); 3、测试数据 int b[5][5] = { //存储某两个有向节点间的权值，代表路径长度，10000代表是无穷。 0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,}; 4、测试结果 七、调试分析 数据结构课程设计 1．在算偏心度的时候；每一列的最大值算错了，下次要注意。 在show的时候也把行和列搞反了；所以以为结果不对其是对的。2．算法的时空分析：(1)时间复杂度:O(n^3)；(2)空间复杂度:O(n^2)[1] 八、遇到的问题及解决办法 1）在算偏心度的时候；每一列的最大值算错了，下次要注意。 解决办法：是把行变，列不变。 2)在show的时候也把行和列搞反了；所以以为结果不对其是对的。 解决办法：把行和列反一下就好。 九、心得体会 Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX)+ Dis(XB)< Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB)= Dis(AX)+ Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。通过这个学习；把Floyd算法搞懂了；模板也熟练了许多。 网络分析（最短路径问题分析） 一、实验目的： 理解最短路径分析的基本原理，学习利用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、心得体会 ：第五篇：ArcGIS网络分析(最短路径问题分析)
点击咨询 