第一篇：最短路徑教案
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網絡分析(最短路徑問題分析)
點擊咨詢 