[發明專利]一種用于Dijkstra算法解最短路徑的教學裝置

無效

• 申請號: 201110378693.4
• 申請日: 2011-11-14
• 公開（公告）號: CN103106814A
• 公開（公告）日: 2013-05-15
• 發明（設計）人: 王遠志
• 申請（專利權）人: 德州學院
• 主分類號: G09B1/08
• 分類號: G09B1/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種教學裝置，尤其是一種用于Dijkstra算法解最短路徑的教學裝置。

背景技術

最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。最常用的路徑算法有：Dijkstra算法、A^*算法、Bellman-Ford算法、SPFA算法(Bellman-Ford算法的改進版本)、Floyd-Warshall算法、Johnson算法、Bi-DirectionBFS算法等。

其中Dijkstra算法是很有代表性的最短路算法，在很多專業課程的教材中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學、計量地理學等等。首先從圖中的一個結點v₁開始，給每一個頂點標一個數，稱為標號。這些標號，又進一步區分為T標號和P標號兩種類型。其中，每一個頂點的T標號表示從起點v₁到該點的最短路徑長度的上界，這種標號為臨時標號；P標號表示從v₁到該點的最短路長度，這種標號為固定標號。在最短路徑計算過程中，對于已經得到P標號的頂點，不再改變其標號；對于凡是沒有標上P標號的頂點，先給它一個T標號；算法的每一步就是把頂點的T標號逐步修改，將其變為P標號。那么，最多經過k-1步，就可以求得到從起點v₁到每一個頂點的最短路徑及其長度。

但是在Dijkstra算法中有一個繁瑣的過程就是比較相應結點的T標號，選出其中最小的將其變為P標號。通過數年教學的經驗來看，學生對上述過程理解的程度差，在解題時此過程的出錯率高，造成最后求解結果的錯誤。鑒于上述問題，設計了本教學裝置。

發明內容

本發明提供一種教學裝置，一種用于Dijkstra算法解最短路徑的教學裝置。

本發明的技術方案為：該教學裝置包括磁性鐵板，圓形鐵片若干和條狀鐵片若干。磁性鐵板為1米*1米，防銹，白色，下部刻畫有五條刻度線，鐵板上部鉆孔兩個。圓形鐵片為黑色，直徑4厘米，上面標有阿拉伯數字1，2-10等。條形鐵片為黑色，寬度為3厘米，長度設置為6厘米、8厘米、10厘米、12厘米、14厘米，每個長度條形鐵片制成10個。

本發明的有益效果：在對以Dijkstra算法解最短路徑的課程內容講解時，利用本教學裝置，可以迅速布置路徑示意圖，并且可以快捷進行圖形的變換。利用磁性鐵板下方的刻度線結合不同長度條形鐵片，可以明晰地對不同結點的T標號進行比較，選擇最小的，對于學生理解Dijkstra算法有很大的幫助。

附圖說明

圖1是本發明的示意圖。

圖1中1是鉆孔，2是磁性鐵板，3圓形鐵片，4是條形鐵片，5是刻度。

具體實施方式

如圖1所示，一種用于Dijkstra算法解最短路徑的教學裝置包括磁性鐵板2、圓形鐵片3、條形鐵片4。磁性鐵板上有鉆孔兩個1，用來懸掛。

在教學中，懸掛該教學裝置，將圓形鐵片3吸附在磁性鐵板2上，3代表圖中的結點。條形鐵片4代表路徑的長度，吸附在2上。路徑布置完畢后，利用同路徑圖中等長的條形鐵片吸附在刻度線5上，用來對比不同結點的T標號。