高職班Dijkstra算法的教學(xué)體會(huì)

許智勇

摘要： 數(shù)學(xué)是一門抽象性、邏輯性很強(qiáng)的課程，數(shù)學(xué)教學(xué)一直就是一個(gè)難題，高職院校的數(shù)學(xué)教師對(duì)此更是頗有同感。教學(xué)中作者感覺求解最短路問(wèn)題的Dijkstra算法難教難學(xué)，初學(xué)者往往覺得算法的思路很簡(jiǎn)單，但動(dòng)起手來(lái)卻不容易計(jì)算正確。如果將算法的計(jì)算過(guò)程用表格表示，認(rèn)真思考每一個(gè)數(shù)據(jù)的來(lái)歷，對(duì)算法的理解和掌握將會(huì)事半功倍。

關(guān)鍵詞： 高職院校Dijkstra算法標(biāo)號(hào)法表格

Dijkstra算法是典型的最短路算法，用于計(jì)算一個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的頂點(diǎn)很多，因此效率低。但Dijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)、圖論、運(yùn)籌學(xué)等。

給定一個(gè)帶權(quán)有向圖，其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)。另外給定圖中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在我們要計(jì)算從源到所有其他各頂點(diǎn)的最短路徑長(zhǎng)度。這里的長(zhǎng)度指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。Dijkstra算法（標(biāo)號(hào)法）是按各頂點(diǎn)與源點(diǎn)間的路徑長(zhǎng)度的遞增次序，生成源點(diǎn)到各頂點(diǎn)的最短路徑的算法，即先求出長(zhǎng)度最短的一條最短路徑，再參照它求出長(zhǎng)度次短的一條最短路徑，依次類推，直到從源點(diǎn)到其他各頂點(diǎn)的最短路徑全部求出為止。

關(guān)于最短路問(wèn)題Dijkstra算法的教學(xué)，看上去不難，但老師講授起來(lái)很費(fèi)勁，學(xué)生學(xué)起來(lái)更加感覺困難。對(duì)此，不尋找恰當(dāng)?shù)慕虒W(xué)方法，一味地啃書本是難以達(dá)到良好的教學(xué)效果的。往往還會(huì)致使學(xué)生厭學(xué)，從而對(duì)相關(guān)課程的學(xué)習(xí)失去興趣。高職學(xué)生相對(duì)于其他普通本科院校的學(xué)生，在數(shù)學(xué)學(xué)習(xí)方面能力要弱一些，因此，高職院校的數(shù)學(xué)教師更應(yīng)該注意尋找適合的教學(xué)方法來(lái)提高學(xué)生的學(xué)習(xí)興趣，從而提高課堂教學(xué)效率。教師應(yīng)改變過(guò)去“填鴨式”、“灌輸式”的教學(xué)方法，充分發(fā)揮學(xué)生的主體作用，靈活運(yùn)用啟發(fā)式教學(xué)方法，激發(fā)學(xué)生思維和質(zhì)疑，培養(yǎng)學(xué)生的創(chuàng)新精神和獨(dú)立探討問(wèn)題的能力。要引導(dǎo)學(xué)生對(duì)問(wèn)題多思考，多問(wèn)幾個(gè)“為什么”，抓住內(nèi)容相關(guān)和相反的部分，對(duì)知識(shí)進(jìn)行橫向和縱向的比較，并掌握它們之間的內(nèi)在聯(lián)系和規(guī)律，培養(yǎng)學(xué)生系統(tǒng)而全面的思維方式。教師應(yīng)鼓勵(lì)學(xué)生主動(dòng)發(fā)表自己的見解，互相探討、啟迪，培養(yǎng)學(xué)生勇于探索，敢于創(chuàng)新的精神，引導(dǎo)學(xué)生自主學(xué)習(xí)。此外，教學(xué)中還應(yīng)注意確保學(xué)生有充分思考的時(shí)間，切實(shí)加強(qiáng)學(xué)生對(duì)問(wèn)題的認(rèn)識(shí)程度，讓高職學(xué)生真正感受到對(duì)數(shù)學(xué)的學(xué)習(xí)并不是那么困難的事情，不斷增強(qiáng)學(xué)習(xí)數(shù)學(xué)的成功感，增強(qiáng)學(xué)習(xí)信心，從而優(yōu)化課堂教學(xué)效果。

。

各行的數(shù)據(jù)是怎么計(jì)算出來(lái)的呢？

例：用Dijkstra算法求下圖從頂點(diǎn)到其余頂點(diǎn)的最短路。

參考文獻(xiàn)：

［1］王信峰.計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)［M］.高等教育出版社，2009.

［2］謝小韋.淺析如何讓學(xué)生學(xué)會(huì)學(xué)習(xí)高職數(shù)學(xué)［J］.學(xué)理論，2010，（36）.

［3］劉志揚(yáng).淺談提高高職數(shù)學(xué)教學(xué)效率的途徑和方法［J］.中國(guó)科教創(chuàng)新導(dǎo)刊，2011，（7）.