第一篇：最短路徑教案

13.4最短路徑問(wèn)題

一、教學(xué)內(nèi)容：本節(jié)課的主要內(nèi)容是利用軸對(duì)稱研究某些最短路徑問(wèn)題，最短路徑問(wèn)題在現(xiàn)實(shí)生活中經(jīng)常遇到，初中階段，主要以“兩點(diǎn)之間，線段最短”“連接直線外一點(diǎn)與直線上各點(diǎn)的所有連線中，垂線段最短”為知識(shí)基礎(chǔ)，有時(shí)還要借助軸對(duì)稱、平移、旋轉(zhuǎn)等變換進(jìn)行研究。

本節(jié)課以數(shù)學(xué)史中的一個(gè)經(jīng)典故事----“將軍飲馬問(wèn)題”為載體開(kāi)展對(duì)“最短路徑問(wèn)題”的課題研究，讓學(xué)生經(jīng)歷將實(shí)際問(wèn)題抽象為數(shù)學(xué)的線段和最小問(wèn)題，再利用軸對(duì)稱將線段和最小問(wèn)題轉(zhuǎn)化為“兩點(diǎn)之間、線段最短”的問(wèn)題。

二、教學(xué)目標(biāo)

1、能利用軸對(duì)稱解決簡(jiǎn)單的最短路徑問(wèn)題

2、再談歲最短路徑的過(guò)程中，體會(huì)“軸對(duì)稱”的橋梁作用，感悟轉(zhuǎn)化的數(shù)學(xué)思想。

三、教學(xué)重難點(diǎn)

重點(diǎn)：利用軸對(duì)稱將最短路徑問(wèn)題轉(zhuǎn)化為“兩點(diǎn)之間、線段最短”問(wèn)題。難點(diǎn)：如何利用軸對(duì)稱將最短路徑問(wèn)題轉(zhuǎn)化為線段和最小問(wèn)題。

四、教學(xué)問(wèn)題診斷

最短路徑問(wèn)題從本質(zhì)上說(shuō)是最值問(wèn)題，作為初中學(xué)生，在此前很少涉及最值問(wèn)題，解決這方面問(wèn)題的數(shù)學(xué)經(jīng)驗(yàn)尚顯不足，特別是面對(duì)具有實(shí)際背景的最值問(wèn)題，更會(huì)感到陌生，無(wú)從下手。

解答“當(dāng)點(diǎn)AB在直線l的同側(cè)時(shí)，如何在l上找到點(diǎn)C，使AC與BC的和最小”，需要將其轉(zhuǎn)化為“直線l異側(cè)的兩點(diǎn)，與直線l上的點(diǎn)的線段的和最小”的問(wèn)題，為什么需要這樣轉(zhuǎn)化，怎樣通過(guò)軸對(duì)稱實(shí)現(xiàn)轉(zhuǎn)化，一些學(xué)生會(huì)存在理解上和操作上的困難。

在證明“最短”時(shí)，需要在直線上任取一點(diǎn)（與所求做的點(diǎn)不重合），證明所連線段和大于所求作的線段和，這種思路和方法，一些學(xué)生想不到。

教學(xué)時(shí)，教師可以讓學(xué)生首先思考“直線l異側(cè)的兩點(diǎn)，與直線l上的點(diǎn)的和最小”為學(xué)生搭建“腳手架”，在證明最短時(shí)，教師要適時(shí)點(diǎn)撥學(xué)生，讓學(xué)生體會(huì)任意的作用。

五、教學(xué)過(guò)程

教師引語(yǔ)：現(xiàn)實(shí)生活中經(jīng)常會(huì)有這樣的生活經(jīng)歷，比如學(xué)校雖然為我們鋪設(shè)了一些石板甬路，方便同學(xué)們的行走，但是很多時(shí)候我們卻并不在這些小路上行走，這樣做的目的是什么呢？（學(xué)生一起回答）如果用數(shù)學(xué)知識(shí)來(lái)解釋這種行為，那就是我們?cè)?jīng)學(xué)習(xí)的“兩點(diǎn)之間、線段最短”或“垂線段最短”，我們稱這樣的問(wèn)題為最短路徑問(wèn)題（板書(shū)課題）現(xiàn)實(shí)生活中經(jīng)常涉及到最短路徑問(wèn)題，這節(jié)課我們學(xué)習(xí)的主要任務(wù)就是最短路徑問(wèn)題，并用所學(xué)知識(shí)探究數(shù)學(xué)史上著名的“將軍飲馬問(wèn)題”。

1、情境引入

相傳，古希臘亞歷山大里亞城里有一位久負(fù)盛名的學(xué)者，名叫海倫，有一天，有一位將軍專門(mén)拜訪海倫，求教一個(gè)百思不得其解的問(wèn)題：從圖中的A地出發(fā)，到一條筆直的河邊飲馬，然后到B地，到河邊什么地方飲馬，可使他所走的路線全程最短？精通數(shù)學(xué)、物理學(xué)的海倫稍加思索，利用軸對(duì)稱的知識(shí)回答了這個(gè)問(wèn)題。這個(gè)問(wèn)題后來(lái)被稱為“將軍飲馬問(wèn)題”。

2、探究解決問(wèn)題的方法

問(wèn)題一：這是一個(gè)實(shí)際問(wèn)題，我們首先把它抽象為數(shù)學(xué)問(wèn)題，請(qǐng)同學(xué)們用自己的語(yǔ)言說(shuō)明這個(gè)問(wèn)題的意思。

師生活動(dòng)：學(xué)生獨(dú)立思考后小組交換意見(jiàn)，然后嘗試回答，相互補(bǔ)充，最后達(dá)成共識(shí)，教師根據(jù)學(xué)生的回答寫(xiě)出問(wèn)題的板書(shū)：如圖，已知點(diǎn)A和點(diǎn)B在直線L的同側(cè)，在直線L上找一點(diǎn)C，使AC與BC的和最小。

設(shè)計(jì)意圖：讓學(xué)生將實(shí)際問(wèn)題抽象為數(shù)學(xué)問(wèn)題，即將最短路徑問(wèn)題抽象為“線段和最小問(wèn)題”。

問(wèn)題二：由上面的問(wèn)題我們可以聯(lián)想到下面的問(wèn)題：A、B分別是直線L異側(cè)的兩點(diǎn)，如何在直線L上找到一點(diǎn)C，使AC與BC的和最?。?/p>

師生活動(dòng)：學(xué)生獨(dú)立思考，畫(huà)圖分析并嘗試回答，教師補(bǔ)充。

問(wèn)題三：對(duì)于第一個(gè)問(wèn)題，如何將點(diǎn)B移到L的另一側(cè)，B′處，滿足直線L上的任一點(diǎn)C，都保持CB與CB′的長(zhǎng)度相等？ 問(wèn)題四：你能利用軸對(duì)稱的知識(shí)找到符合條件的點(diǎn)B′嗎？

師生活動(dòng)：學(xué)生獨(dú)立考，嘗試畫(huà)圖，然后小組交流，學(xué)生代表匯報(bào)交流成果，師生共同補(bǔ)充：只要作出點(diǎn)B關(guān)于直線L的對(duì)稱點(diǎn)B′，就可以滿足CB=CB′,再利用問(wèn)題二中的方法，連接AB′,則AB′與直線L的交點(diǎn)即為所求。

學(xué)生敘述，教師板書(shū)并畫(huà)圖，同時(shí)學(xué)生在練習(xí)本上畫(huà)圖。

設(shè)計(jì)意圖：通過(guò)搭建臺(tái)階，為學(xué)生探究問(wèn)題提供“腳手架”將同側(cè)難以解決的問(wèn)題提轉(zhuǎn)化為異側(cè)容易解決的問(wèn)題，滲透轉(zhuǎn)化思想。

3、推理證明“最短”

問(wèn)題五：你能用所學(xué)的知識(shí)證明AC+BC最短嗎？

師生活動(dòng)：師生共同分析，然后學(xué)生說(shuō)證明過(guò)程，教師板書(shū)。

證明：在直線L上任取一點(diǎn)C′（與點(diǎn)C不重合），連接AC′,BC′,B′C′.由軸對(duì)稱的性質(zhì)可知，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最短。

問(wèn)題六：這里任取一點(diǎn)C′的作用是什么？

師生活動(dòng)：學(xué)生相互交流，教師適時(shí)點(diǎn)撥，最后達(dá)成共識(shí)：若直線L上任取一點(diǎn)C′與A、B兩點(diǎn)的距離之和都大于AC+BC，則說(shuō)明AC+BC最短。

設(shè)計(jì)意圖：讓學(xué)生進(jìn)一步體會(huì)做法的正確性，提高邏輯思維能力。

問(wèn)題七：回顧前面的探究過(guò)程，我們是通過(guò)怎樣的過(guò)程、借助什么解決問(wèn)題的？

師生共同總結(jié)：首先作其中一點(diǎn)關(guān)于直線的對(duì)稱點(diǎn)，然后連接另一點(diǎn)與對(duì)稱點(diǎn)之間的線段，通過(guò)軸對(duì)稱將兩條線段和轉(zhuǎn)化到同一條線段上去，這條線段與直線的交點(diǎn)即為所求，整個(gè)過(guò)程利用了“軸對(duì)稱”和“兩點(diǎn)之間、線段最短“的知識(shí)。

設(shè)計(jì)意圖：讓學(xué)生在反思的過(guò)程中，體會(huì)軸對(duì)稱的“橋梁”作用，感悟轉(zhuǎn)化思想，豐富數(shù)學(xué)活動(dòng)經(jīng)驗(yàn)。

4、鞏固練習(xí)

（1）如圖，一艘旅游船從大橋AB的P處前往山腳下的Q處接游客，然后將游客送往河岸BC上，再回到P處，請(qǐng)畫(huà)出旅游船的最短路徑。

師生活動(dòng)：學(xué)生分析解題思路，并相互補(bǔ)充，然后獨(dú)立完成畫(huà)圖，學(xué)生代表上臺(tái)講解?；舅悸贩治觯捍祟}中輪船的行走路線共有三段，其中PQ是必經(jīng)路段，由“兩點(diǎn)之間，線段最短”需首先連接PQ，再將河岸BC看成一條直線，這樣問(wèn)題就轉(zhuǎn)化為“點(diǎn)P、Q在直線BC同側(cè)，如何在BC上找一點(diǎn)R，使PR+QR最小”。

設(shè)計(jì)意圖：讓學(xué)生進(jìn)一步鞏固解決最短路徑問(wèn)題的基本策略和基本方法。

（2）如圖，∠XOY內(nèi)有一點(diǎn)P，在射線OX上找出一點(diǎn)M，在射線OY上找出一點(diǎn)N，使PM+MN+NP最短．

分析：此題的出題背景就是角。本題主要利用了兩點(diǎn)之間線段最短的性質(zhì)通過(guò)軸對(duì)稱圖形的性質(zhì)確定三角形的另兩點(diǎn)．

分別以直線OX、OY為對(duì)稱軸，作點(diǎn)P的對(duì)應(yīng)點(diǎn)P1與P2，連接P1P2交OX于M，交OY于N，則PM+MN+NP最短．

5、課堂小結(jié)：教師與學(xué)生一起回顧本節(jié)課所學(xué)主要內(nèi)容，并請(qǐng)學(xué)生回答：（1）本節(jié)課研究問(wèn)題的基本過(guò)程是什么？（2）軸對(duì)稱在所研究的問(wèn)題中起到什么作用？

6、布置作業(yè)：《課時(shí)練》第49頁(yè)1、2、3、4、5、7、8、9

第二篇：最短路徑教案

最短路徑問(wèn)題

教學(xué)目標(biāo)：

1.理解并掌握平面內(nèi)一條直線同側(cè)兩個(gè)點(diǎn)到直線上的某一點(diǎn)距離之和為最小值時(shí)點(diǎn)的位置的確定。

2.能利用軸對(duì)稱平移解決實(shí)際問(wèn)題中路徑最短的問(wèn)題。

3.通過(guò)獨(dú)立思考，合作探究，培養(yǎng)學(xué)生運(yùn)用數(shù)學(xué)知識(shí)解決實(shí)際問(wèn)題的基本能力，感受學(xué)習(xí)成功的快樂(lè)。

教學(xué)重點(diǎn)：

將實(shí)際問(wèn)題轉(zhuǎn)化成數(shù)學(xué)問(wèn)題，運(yùn)用軸對(duì)稱平移解決生活中路徑最短的問(wèn)題，確定出最短路徑的方法。

教學(xué)難點(diǎn)：

探索發(fā)現(xiàn)“最短路徑”的方案，確定最短路徑的作圖及原理。

導(dǎo)學(xué)過(guò)程：

一、創(chuàng)設(shè)情景，引入新知。

前面我們研究過(guò)一些關(guān)于“兩點(diǎn)的所有連線中，線段最短”、“連接直線外一點(diǎn)與直線上各點(diǎn)的所有線段中，垂線段最短”等的問(wèn)題，我們稱它們?yōu)樽疃搪窂絾?wèn)題．現(xiàn)實(shí)生活中經(jīng)常涉及到選擇最短路徑的問(wèn)題，本節(jié)將利用數(shù)學(xué)知識(shí)探究實(shí)際生活中的最短路徑問(wèn)題。

二、自主學(xué)習(xí)，探究新知。

問(wèn)題1（將軍飲馬問(wèn)題）

牧馬人從A地出發(fā)，到一條筆直的河邊L飲馬，然后到B地，牧馬人到河邊什么地方飲馬，可使所走的路徑最短？

2、探索問(wèn)題：

教師提出問(wèn)題，引導(dǎo)學(xué)生思考：

（1）如何將這個(gè)實(shí)際問(wèn)題轉(zhuǎn)化為數(shù)學(xué)問(wèn)題？轉(zhuǎn)化的要點(diǎn)是什么？

（2）回憶以前學(xué)過(guò)的“最短”的知識(shí)點(diǎn)，（兩點(diǎn)之間，線段最短；垂線段最短），思考：這個(gè)問(wèn)題中的“最短”和以前學(xué)過(guò)的知識(shí)有什么相同點(diǎn)和不同點(diǎn)？（3）、如何把“不同點(diǎn)”化為“相同點(diǎn)”？（4）、如何用圖形將問(wèn)題展現(xiàn)出來(lái)？

【學(xué)生活動(dòng)】：學(xué)生獨(dú)立思考，畫(huà)圖分析，并嘗試回答，相互補(bǔ)充，師生共同歸納：（1）、將A、B兩地抽象為兩個(gè)點(diǎn)，將河L抽象為一條直線（如圖2），則問(wèn)題轉(zhuǎn)化為：如何在L上找一點(diǎn)C，使AC與BC的和最?。ㄈ鐖D3）。轉(zhuǎn)化時(shí)要注意條件和結(jié)論的轉(zhuǎn)化，以及點(diǎn)、線的抽象。

（2）、相同點(diǎn)：都是兩點(diǎn)間的最短距離問(wèn)題。

不同點(diǎn)：一個(gè)是兩點(diǎn)在L的同側(cè)；一個(gè)是兩點(diǎn)在L的異側(cè)，并畫(huà)圖比較（如圖4）。（3）利用軸對(duì)稱的知識(shí)找出B點(diǎn)關(guān)于直線L的對(duì)稱點(diǎn)B′,就可以滿足C B′= CB,再連接A B′，則A B′與直線L的交點(diǎn)C極為所求。

【教師板書(shū)并畫(huà)圖】（如圖5）

第一步：作出B點(diǎn)關(guān)于直線L的對(duì)稱點(diǎn)B′

第二步：連接A B′，與直線L的交點(diǎn)為C,則C點(diǎn)即為所求。

證明：略

問(wèn)題二（造橋選址問(wèn)題）如圖,A和B兩地在一條河的兩岸,現(xiàn)要在河上造一座橋MN.橋造在何處可使從A到B的路徑AMNB最短?（假定河的兩岸是平行的直線,橋要與河垂直.)

將實(shí)際問(wèn)題中A，B兩地與筆直的河L抽象成 點(diǎn)A.點(diǎn)B和直線a，b.如圖：

分析：AM+NB最短，要先確定點(diǎn)N在直線b的位置，如果我先將A點(diǎn)往直線a的垂直方向平移MN個(gè)單位 后到A′，由于MN垂直直線a，N點(diǎn)就是M點(diǎn)往直線 b的垂直方向平移MN個(gè)單位后到的點(diǎn)，由圖形平移后 的對(duì)應(yīng)點(diǎn)之間的線段是平行且相等的，得到AM=A′N.AM+NB最短即A′N+NB最短.轉(zhuǎn)變成了直線b上是找 到一點(diǎn)N，使A′ N+NB最短,連結(jié)A′,B,與直線b相交的 一點(diǎn)為N點(diǎn).證明略.三、鞏固練習(xí)：

1.∠WXZ內(nèi)有一點(diǎn)Z，在WZ，ZY上分別有點(diǎn)A，B,當(dāng)△ABZ的周長(zhǎng)最小時(shí)，請(qǐng)?jiān)趫D中作出點(diǎn)A，B的位置.2.如圖，A、B兩地之間有兩條河，現(xiàn)要在兩條河上各造一座橋MN和PQ.橋分別建在何處才能使從A到B的路徑最短？（假定河的兩岸是平行的直線，橋要與河岸垂直）

四、課堂小結(jié)

1、本節(jié)主要知識(shí)點(diǎn)：

軸對(duì)稱的對(duì)稱知識(shí)和兩點(diǎn)間的最短距離在“最短路徑”這類問(wèn)題中的運(yùn)用。實(shí)際問(wèn)題與數(shù)學(xué)問(wèn)題的轉(zhuǎn)化。

2、提出問(wèn)題： 這節(jié)課你們學(xué)到了什么？還有哪些疑惑？

五、布置作業(yè)

新觀察

第三篇：《最短路徑》教學(xué)反思

11月23號(hào)下午第三節(jié)，我講了公開(kāi)課《最短路徑》第一課時(shí)，學(xué)校領(lǐng)導(dǎo)及沒(méi)課的老師來(lái)到報(bào)告廳聽(tīng)課，聽(tīng)課后田校長(zhǎng)對(duì)我講的這一節(jié)課經(jīng)行了點(diǎn)評(píng)，我受益匪淺，所以把感悟以及所學(xué)到的總結(jié)如下：

1、問(wèn)題設(shè)計(jì)要有啟發(fā)性。在設(shè)計(jì)問(wèn)題的時(shí)候不可以設(shè)計(jì)無(wú)用的問(wèn)題，要讓學(xué)生真正有所思考，并且可以經(jīng)過(guò)思考可以得到結(jié)論，在設(shè)計(jì)問(wèn)題的時(shí)候也不要設(shè)計(jì)太難的問(wèn)題，打擊學(xué)生的積極性，要把難的問(wèn)題分解，解剖成簡(jiǎn)單的小問(wèn)題一步步來(lái)解決。

2、課堂引入，要更加的正規(guī)，不能太隨意。比如在引入的時(shí)候可以用螞蟻找食物的實(shí)例引入，可以更形象。

3、引入之后，要復(fù)習(xí)預(yù)備知識(shí)。因?yàn)樗械闹R(shí)都是在舊知識(shí)的基礎(chǔ)上生成的，如果說(shuō)新知識(shí)是冰川露出大海的部分，那舊知識(shí)就是藏在大海中的更大的部分，所以要強(qiáng)調(diào)從舊知識(shí)的基礎(chǔ)上生成新知識(shí)，調(diào)動(dòng)舊知識(shí)環(huán)境，衍生新知識(shí)，這樣有利于學(xué)生形成數(shù)學(xué)體系，所學(xué)的內(nèi)容也不會(huì)讓學(xué)生感覺(jué)太突兀，而是自然而然的得到。所以要認(rèn)真分析預(yù)備知識(shí)，把新知識(shí)放在舊知識(shí)的基礎(chǔ)上，通過(guò)復(fù)習(xí)慢慢引出新的內(nèi)容，這樣學(xué)生更容易掌握，更容易接受，不會(huì)產(chǎn)生畏難情緒，反而覺(jué)得清松自如。

4、授課的過(guò)程中應(yīng)該環(huán)環(huán)相扣，一步步上，要講問(wèn)題分解，化大為小，化難為易，化繁為簡(jiǎn)，降低難度，就像是上臺(tái)階，一個(gè)個(gè)的臺(tái)階上。

5、注重建模思想。雖然不必要提出來(lái)這個(gè)名詞，但是要讓學(xué)生能從實(shí)際問(wèn)題中抽象出數(shù)學(xué)問(wèn)題，本節(jié)課的“將軍飲馬問(wèn)題”就是一個(gè)實(shí)際的問(wèn)題，要讓學(xué)生轉(zhuǎn)換成數(shù)學(xué)問(wèn)題，抽象出數(shù)學(xué)問(wèn)題。

第四篇：最短路徑_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告

設(shè)計(jì)題目：____醫(yī)院選址____________ 姓名：__________________ 學(xué)號(hào)：________________ 專業(yè)：___________

院系：____________

班級(jí)：_________________ 指導(dǎo)教師：_________________

年 1月 3 日

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

一、問(wèn)題描述

(1)題目?jī)?nèi)容：有n個(gè)村莊，現(xiàn)要從這n個(gè)村莊中選擇一個(gè)村莊新建一所醫(yī)院，使其余的村莊到這所醫(yī)院的距離總和來(lái)說(shuō)較短。（n>=5）(2)基本要求：

(3)可以輸出每一對(duì)點(diǎn)間的路徑長(zhǎng)度；然后選取偏心度，最小的偏心度即為所求。

二、需求分析

(4)本程序的功能包括找出每一對(duì)點(diǎn)間的路徑長(zhǎng)度。(5)然后算出每一對(duì)點(diǎn)的偏心度。(6)其中最小的偏心度即為所求。

三、概要設(shè)計(jì)

操作集合：

(7)public:MGraph(DataType a[],int b[][MaxSize],int n,int e);//初始化鄰接矩陣和路徑

(8)void Floyd();//弗洛伊德算法的實(shí)現(xiàn)(9)void getE();//獲取偏心度

(10)void showdist();//把每一對(duì)頂點(diǎn)之間的路徑權(quán)值show出來(lái)(11)~MGraph(){} //類的析構(gòu)函數(shù)

四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

(1)DataType vertex[MaxSize];//存放圖中頂點(diǎn)的數(shù)組(2)int

arc[MaxSize][MaxSize];//存放圖中邊的數(shù)組

(3)string path[MaxSize][MaxSize];//存放從Vi到Vj的最短路徑，初始為

//path[i][j]=“ViVj”

(4)int dist[MaxSize][MaxSize];//存放求得的最短路徑長(zhǎng)度(5)int vertexNum, arcNum;//圖的頂點(diǎn)數(shù)和邊數(shù)(6)int E[MaxSize][2];//獲取最小偏心度和該頂點(diǎn)

五、算法設(shè)計(jì)

1.算法分析

1）對(duì)帶權(quán)有向圖的，調(diào)用Floyd算法，對(duì)每一對(duì)頂點(diǎn)間的最短路徑長(zhǎng)度的矩陣；

2）對(duì)最短路徑長(zhǎng)度矩陣的每列求最大值，即得到各點(diǎn)的偏心度； 3)具有最小偏心度的頂點(diǎn)即為所求。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

2.算法實(shí)現(xiàn)

#include #include #include using namespace std;

const int MaxSize = 5;template class MGraph { public:，建立具有n個(gè)頂點(diǎn)e條邊的圖

};template MGraph::MGraph(DataType a[], int b[][MaxSize],int n,int e){

} template void MGraph::Floyd(){ int i,j,k;

MGraph(DataType a[], int b[][MaxSize],int n,int e);//構(gòu)造函數(shù)

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];

//存放圖中頂點(diǎn)的數(shù)組 //存放圖中邊的數(shù)組 //存放求得的最短路徑長(zhǎng)度 //圖的頂點(diǎn)數(shù)和邊數(shù) 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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

} for(i=0;i

} for(k=0;k

for(i=0;i

}

//頂點(diǎn)i和j之間是否經(jīng)過(guò)頂點(diǎn)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 void MGraph::showdist(){

} template void MGraph::getE(){

心度。

} for(int i=0;i

}

for(int i=0;i

} for(int j=0;j

“;for(int i=0;i

E[i][0]=i;//存放某一個(gè)節(jié)點(diǎn)的序號(hào) E[i][1]=0;//存放節(jié)點(diǎn)的最短路徑，權(quán)值。

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];

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

cout<

} void main(){

代表是無(wú)窮。

}

MGraph GM(a,b,5,7);GM.Floyd();GM.showdist();cout<

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是節(jié)點(diǎn)的信息，代表某一個(gè)地點(diǎn)。

//存儲(chǔ)某兩個(gè)有向節(jié)點(diǎn)間的權(quán)值，代表路徑長(zhǎng)度，10000 int min=E[0][1],k;for(int i=0;i

} cout<<”最佳選址為“<

cout<

if(E[i][1]

} min=E[i][1];k=i;

六、程序測(cè)試與實(shí)現(xiàn)

1、函數(shù)之間的調(diào)用關(guān)系

Main

Floyd()

showdist()

getE()

2、主程序

void main(){ char a[5] = {'A','B','C','D','E'};

//鄰接矩陣,A,B...是節(jié)點(diǎn)的信息，代表某一個(gè)地點(diǎn)。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

int b[5][5] = { //存儲(chǔ)某兩個(gè)有向節(jié)點(diǎn)間的權(quán)值，代表路徑長(zhǎng)度，10000代表是無(wú)窮。

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(a,b,5,7);

}

GM.Floyd();

GM.showdist();

cout<

GM.getE();

3、測(cè)試數(shù)據(jù)

int b[5][5] = { //存儲(chǔ)某兩個(gè)有向節(jié)點(diǎn)間的權(quán)值，代表路徑長(zhǎng)度，10000代表是無(wú)窮。

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、測(cè)試結(jié)果

七、調(diào)試分析

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1．在算偏心度的時(shí)候；每一列的最大值算錯(cuò)了，下次要注意。

在show的時(shí)候也把行和列搞反了；所以以為結(jié)果不對(duì)其是對(duì)的。2．算法的時(shí)空分析：(1)時(shí)間復(fù)雜度:O(n^3)；(2)空間復(fù)雜度:O(n^2)[1]

八、遇到的問(wèn)題及解決辦法

1）在算偏心度的時(shí)候；每一列的最大值算錯(cuò)了，下次要注意。

解決辦法：是把行變，列不變。

2)在show的時(shí)候也把行和列搞反了；所以以為結(jié)果不對(duì)其是對(duì)的。

解決辦法：把行和列反一下就好。

九、心得體會(huì)

Floyd算法的基本思想如下：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過(guò)若干個(gè)節(jié)點(diǎn)X到B。所以，我們假設(shè)Dis(AB)為節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)X，我們檢查Dis(AX)+ Dis(XB)< Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設(shè)置Dis(AB)= Dis(AX)+ Dis(XB)，這樣一來(lái)，當(dāng)我們遍歷完所有節(jié)點(diǎn)X，Dis(AB)中記錄的便是A到B的最短路徑的距離。通過(guò)這個(gè)學(xué)習(xí)；把Floyd算法搞懂了；模板也熟練了許多。

第五篇：ArcGIS網(wǎng)絡(luò)分析(最短路徑問(wèn)題分析)

網(wǎng)絡(luò)分析（最短路徑問(wèn)題分析）

一、實(shí)驗(yàn)?zāi)康模?/p>

理解最短路徑分析的基本原理，學(xué)習(xí)利用arcgis軟件進(jìn)行各種類型的最短路徑分析的操作。

二、實(shí)驗(yàn)準(zhǔn)備

1、實(shí)驗(yàn)背景：

最短路徑分析是空間網(wǎng)絡(luò)分析中最基本的應(yīng)用，而交通網(wǎng)絡(luò)中要素的設(shè)置對(duì)最短路徑的選擇有著很大的影響。實(shí)驗(yàn)要求根據(jù)不同的權(quán)重，給出到達(dá)指定目的地的路徑選擇方案，并給出路徑長(zhǎng)度。

? 在網(wǎng)絡(luò)中指定一個(gè)超市，要求分別求出在距離、時(shí)間限制上從家到超市的最佳路徑。

? 給定訪問(wèn)順序，按要求找出從家經(jīng)逐個(gè)地點(diǎn)達(dá)到目的地的最佳路徑。

2、實(shí)驗(yàn)材料：

軟件：ArcGIS Desktop 9.x，實(shí)驗(yàn)數(shù)據(jù)：文件夾ex6中，一個(gè)GeoDatabase地理數(shù)據(jù)庫(kù)：City.mdb，內(nèi)含有城市交通網(wǎng)、超市分布圖，家庭住址以及網(wǎng)絡(luò)關(guān)系。

三、實(shí)驗(yàn)內(nèi)容及步驟

首先啟動(dòng)ArcMap，選擇ex6city.mdb，再雙擊后選擇將整個(gè)要素?cái)?shù)據(jù)集“city”加載進(jìn)來(lái)，然后將“place”點(diǎn)狀要素以“HOME”字段屬性值進(jìn)行符號(hào)化，1值是家，0值是超市。

第1步 無(wú)權(quán)重最佳路徑的選擇 ? 加載 “設(shè)施網(wǎng)絡(luò)分析”工具條（“視圖”>>“工具條”，勾選“設(shè)施網(wǎng)絡(luò)分析”），點(diǎn)選旗標(biāo)和障礙工具板下拉箭頭，將旗標(biāo)放在家和想要去的超市點(diǎn)上。

第2步 加權(quán)最佳路徑選擇

? 在設(shè)施網(wǎng)絡(luò)分析工具條上，點(diǎn)選旗標(biāo)和障礙工具板下拉箭頭，將旗標(biāo)放在家和想去的某個(gè)超市點(diǎn)上。

? 選擇“分析”下拉菜單，選擇“選項(xiàng)”按鈕，打開(kāi)“分析選項(xiàng)”對(duì)話框，選擇“權(quán)重”標(biāo)簽頁(yè)，在“邊權(quán)重”上，全部選擇長(zhǎng)度“l(fā)ength”權(quán)重屬性。? 點(diǎn)選“追蹤任務(wù)”下拉菜單選擇“查找路徑”。單擊“執(zhí)行”鍵，則以長(zhǎng)度為比重為基礎(chǔ)的最短路徑將顯示出來(lái)，這條路徑的總成本將顯示在狀態(tài)列。

?? 上述是通過(guò)距離的遠(yuǎn)近選擇而得到的最佳路徑，而不同類型的道路由于道路車流量的問(wèn)題，有時(shí)候要選擇時(shí)間較短的路徑，同樣可以利用網(wǎng)絡(luò)分析進(jìn)行獲得最佳路徑。

第3步 按要求和順序逐個(gè)對(duì)目的點(diǎn)的路徑的實(shí)現(xiàn)

? 在設(shè)施網(wǎng)絡(luò)分析工具條上，點(diǎn)選旗標(biāo)和障礙工具板下拉箭頭，將旗標(biāo)按照車輛訪問(wèn)的順序逐個(gè)放在點(diǎn)上。

? 選擇“分析”下拉菜單，選擇“選項(xiàng)”按鈕，打開(kāi)“分析選項(xiàng)”對(duì)話框，選擇“權(quán)重”標(biāo)簽頁(yè)，在“邊權(quán)重”上，全部選擇長(zhǎng)度“l(fā)ength”權(quán)重屬性。? 點(diǎn)選“追蹤任務(wù)”下拉菜單選擇“查找路徑”。單擊“執(zhí)行”鍵，則從起點(diǎn)按順序逐一經(jīng)過(guò)超市最后回到家的最短有效路徑將顯示出來(lái)，這條路徑的總成本將顯示在狀態(tài)列。

同樣是經(jīng)過(guò)這11個(gè)地點(diǎn)，換成權(quán)重是時(shí)間的，由于道路車流量的不同，如在市中心車流量特別大，車速慢，故而為節(jié)約時(shí)間，所以使得路徑發(fā)生很大的改變。

第4步 阻強(qiáng)問(wèn)題

這里的阻強(qiáng)是指網(wǎng)絡(luò)中的點(diǎn)狀要素或線狀要素因?yàn)閷?shí)際中遇到的例如修路，或那個(gè)時(shí)段車輛飽和，十字路口發(fā)生事故等一些緣故而使得要素不可運(yùn)行，這時(shí)原來(lái)獲得的最短路徑就需要進(jìn)行修正，具體操作如下： 修路的情形出現(xiàn)，即某個(gè)路段不可運(yùn)行，這在網(wǎng)絡(luò)中的表現(xiàn)是設(shè)置阻強(qiáng)，方法有兩種，一種是永久性的，直接將網(wǎng)絡(luò)邊要素的屬性修改成不可運(yùn)行。選擇要進(jìn)行設(shè)置的邊要素，將其屬性中的“Enabled”字段改成“False”即可；另一種是暫時(shí)性的，設(shè)置邊要素障礙。即利用邊要素障礙添加工具將邊設(shè)置。

?

4、心得體會(huì) ：