五階遞進的最短路徑問題教學模式探索

許項東 徐詠蕾 鄒曉磊 滕靖

摘? 要：最短路徑問題是計算機科學、地理信息科學、運籌學、管理科學、交通工程、工業(yè)工程和復雜系統(tǒng)科學等領域的基礎性問題，也是許多相關課程中的教學重點。針對目前教學中存在的被動接受、手工計算、只算不用等問題，按照“精選算法、縱向到底、橫向到邊”的教學理念，探索“算法原理—數(shù)學建?！獞门e例—程序?qū)崿F(xiàn)—算法比賽”五階遞進的最短路徑問題教學模式，有助于培養(yǎng)和提升學生的原理掌握深度、優(yōu)雅學術(shù)品位、運籌優(yōu)化思維、綜合應用能力和團隊合作精神。

關鍵詞：圖論；最短路徑；數(shù)學建模；Dijkstra算法；應用舉例

中圖分類號：G642? ? ? 文獻標志碼：A? ? ? ? ? 文章編號：2096-000X（2023）32-0032-04

Abstract： The shortest path problem is a fundamental problem and a core knowledge module in many disciplines， such as computer science， geographic information system， operations research， management science， transportation engineering， industrial engineering， and complex system science. It is also the focus of teaching in many related courses. According to the teaching concept of "selecting algorithms， vertical to the end， horizontal to the edge"， this paper explores the five-step teaching mode of "algorithm principle - mathematical modeling - application example - program realization - algorithm competition" for the shortest path. It is helpful to cultivate and enhance students' in-depth grasp of principles， elegant academic taste， operation and optimization thinking， comprehensive application ability， and team spirit.

Keywords： graph theory; shortest path problem; mathematical modeling; Dijkstra algorithm; applications demonstration

基金項目：上海高校市級重點課程建設項目“《運籌學》”（無編號）；上海高校課程思政領航課程建設項目“《運籌學》”（無編號）

第一作者簡介：許項東（1985-），男，漢族，安徽霍山人，博士，教授，博士研究生導師。研究方向為交通運輸網(wǎng)絡建模與優(yōu)化、交通系統(tǒng)韌性。

最短路徑問題的目標是，在網(wǎng)絡中給定兩節(jié)點之間找出一條總權(quán)重之和最小的路徑[1]。作為圖論中最為經(jīng)典與最常見的問題之一，最短路徑問題是計算機科學、地理信息科學、運籌學、管理科學、交通運輸工程、工業(yè)工程和復雜系統(tǒng)科學等領域的研究理論基礎，其核心思想與日常生活中的交通導航、救災搶險、工程管理等密切相關，成為許多相關課程的教學重點。

最短路徑問題是運籌學課程的基本內(nèi)容和教學重點。以同濟大學為例，如表1所示，開設運籌學課程的學院和專業(yè)主要有：交通運輸工程學院的交通工程、交通運輸專業(yè)，經(jīng)濟與管理學院的物流管理、信息管理與信息系統(tǒng)、市場營銷等專業(yè)，數(shù)學科學學院的統(tǒng)計學、數(shù)學與應用數(shù)學專業(yè)，機械與能源工程學院的工業(yè)工程專業(yè)等。需要指出的是，這里僅統(tǒng)計了運籌學類課程。其他課程中也可能涵蓋最短路徑問題，如計算機相關專業(yè)的數(shù)據(jù)結(jié)構(gòu)與算法課程。

由于最短路徑問題模型目標明確、求解算法啟發(fā)性強、與其他問題結(jié)合度高及應用場景廣泛，是一個培養(yǎng)創(chuàng)新思維和實踐能力的絕佳教學點。然而，在目前的最短路徑問題教學中，“被動接受、手工計算、只算不用”的問題仍普遍存在，學生們的綜合能力與應用水平有待提高。在內(nèi)容上，重課本輕實踐，實際問題的數(shù)學抽象能力較弱[2-3]；在思維上，重解題輕原理，只會快速解題而舉一反三能力欠缺；在方法上，重手算輕程序，不會主動應用計算機與先進工具來輔助求解[4-5]。上述問題使得我們的教學實際效果難以滿足新時代對高校人才培養(yǎng)的要求，尤其是與研究型大學培養(yǎng)創(chuàng)新精神與實踐能力兼?zhèn)涞娜瞬拍繕舜嬖谳^大差距[6]。本教學團隊經(jīng)過多年的教學探索和迭代反饋，初步形成并較為成功地實踐了可復制可推廣的“算法原理—數(shù)學建模—應用舉例—程序?qū)崿F(xiàn)—算法比賽”五階遞進的最短路徑問題教學模式，以期給其他有類似問題的本科課程教學以方法上的參考。

一? 五階遞進的最短路徑問題教學模式

針對現(xiàn)有最短路徑教學中存在的問題，我們基于“精選算法、縱向到底、橫向到邊”的教學理念，提出了“算法原理—數(shù)學建?！獞门e例—程序?qū)崿F(xiàn)—算法比賽”五階遞進的最短路徑問題教學模式，如圖1所示。其中，“算法原理、數(shù)學建模、應用舉例”主要為課內(nèi)教學部分，從概念到方法再到實例，由淺入深、層層遞進。考慮到最短路徑算法譜系較為復雜，通過“精選算法”，為學生講細講透一種經(jīng)典算法原理，夯實基礎理論。按照“縱向到底”的理念，深入介紹其數(shù)學規(guī)劃模型與實際應用，幫助學生深化理解算法。“程序?qū)崿F(xiàn)、算法比賽”則為課外實踐部分，基于“橫向到邊”的思想，從小規(guī)模測試網(wǎng)絡的算例實驗，到大規(guī)模真實網(wǎng)絡（所在城市的道路交通網(wǎng)絡）的算法設計與優(yōu)化，引導學生化被動為主動，注重提升學生的實踐應用能力與創(chuàng)新思維，以及加強與前修課程的綜合理解。通過課堂內(nèi)外相互促進、相互結(jié)合的形式，形成五階遞進的最短路徑問題教學模式。

在最短路徑問題引入方面，考慮到筆者的課程教學對象是交通運輸工程學院的本科生（包括交通工程專業(yè)、交通運輸專業(yè)），我們引入了日常生活中常用且也是交通運輸工程的前沿應用場景——車輛路徑導航（包括未來自動駕駛的路徑導航）。

最短路徑問題的具體算法有著較為豐富和成熟的譜系，可按照以下三類進行細分[7]：①問題類型（Problem Type），如針對單源最短路徑的Dijkstra算法，針對多源最短路徑的Floyd算法；②輸入網(wǎng)絡特征（Input Network Characteristics），如針對無向網(wǎng)絡的Minty算法、針對整數(shù)弧長的Dial算法；③求解策略（Solution Techniques），如針對網(wǎng)絡變化時最短路徑更新迭代的Loubal算法、應用模擬計算機技術(shù)的Klee算法等。

在教學實踐中，我們遵循“精選算法、縱向到底、橫向到邊”的教學理念。其中，“精選算法”指的是，我們在課堂教學中重點介紹最為經(jīng)典且常用的Dijkstra算法，對其他算法只簡單提及，留給學生課后自學和拓展；“縱向到底”指的是我們不僅講授Dijkstra算法的執(zhí)行步驟，更啟發(fā)學生理解算法基本原理和數(shù)學規(guī)劃建模過程，引導學生品味該算法的創(chuàng)新之處和優(yōu)雅之美；“橫向到邊”指的是，我們引導學生利用熟悉的計算機語言來編寫Dijkstra算法的代碼，結(jié)合大規(guī)模真實交通網(wǎng)絡，挖掘算法結(jié)果所蘊含的管理洞見，并通過以小組為單位的算法比賽培養(yǎng)和提升學生的綜合應用能力、團隊合作精神。

經(jīng)過多年的教學實踐，在算法原理環(huán)節(jié)提升了學生的優(yōu)雅學術(shù)品位；通過介紹最短路徑問題的數(shù)學規(guī)劃建模，引領學生形成看透問題本質(zhì)的意識；通過貼近專業(yè)方向的多個應用舉例，幫助學生開拓聯(lián)想創(chuàng)新思維；通過程序?qū)崿F(xiàn)，鍛煉學生的綜合應用能力，再通過算法實現(xiàn)，積累了學生團隊合作與創(chuàng)新實戰(zhàn)經(jīng)驗。

二? 教學設計與實踐

（一）? 算法原理——優(yōu)雅學術(shù)品位

在算法原理部分，我們依循經(jīng)典運籌學教材的講解思路，介紹最短路徑問題的數(shù)學定義、經(jīng)典Dijkstra算法（包括適合初學的圖上作業(yè)法、適合程序?qū)崿F(xiàn)的表上作業(yè)法）等。在介紹算法原理的同時，我們注重引入算法的發(fā)展演化歷史，引導學生思考不同算法的優(yōu)缺點和適用條件，培養(yǎng)學生的優(yōu)雅學術(shù)品位。如用枚舉法亦可找到最短路徑，但并不高效，計算機技術(shù)的進步催生了更簡便高效的算法，使得最短路徑問題的求解更加簡潔巧妙。

（二）? 數(shù)學建?！角髥栴}本質(zhì)

在現(xiàn)有的經(jīng)典運籌學教材中，最短路徑問題部分少有介紹其數(shù)學規(guī)劃模型，我們在教學中適度介紹最短路徑問題的數(shù)學規(guī)劃模型。之所以在教學中涉及最短路徑問題的數(shù)學建模，是為了幫助學生進一步了解最短路徑問題的本質(zhì)，深化對最短路徑算法的理解。在研究現(xiàn)實世界的很多復雜問題時，通常是先進行數(shù)學建模，然后針對模型開發(fā)高效的求解算法。

作為數(shù)學規(guī)劃模型，涉及變量、目標函數(shù)、約束條件等三要素。在教學中，引導學生思考最短路徑問題的變量、目標函數(shù)、約束條件分別是什么。決策變量的選取，直接決定模型是否需要計算量和存儲量高昂的路徑枚舉。按照最短路徑問題的定義，一般將表征每個邊是否被選入最短路徑的0-1整數(shù)變量作為求解變量，目標函數(shù)是全網(wǎng)所有被選中邊的總成本最小，約束條件需要確保所有被選中邊可以構(gòu)成從起點到終點之間唯一的一條路徑，即從起點有且只有一條邊被選中，中間節(jié)點（非起點、非終點）的流入和流出守恒，進入終點有且只有一條邊被選中。尤其要關注，該模型的0-1整數(shù)求解變量可等價松弛為非負連續(xù)變量，從而將0-1整數(shù)線性規(guī)劃問題轉(zhuǎn)化為更易求解的線性規(guī)劃。引導學生體會，在對模型進行求解前，非常有必要“三思而后行”，避免“Garbage in， garbage out”現(xiàn)象，盡可能降低模型的復雜性，在算法的通用性和定制化之間作出合適的取舍。

（三）? 應用舉例——聯(lián)想創(chuàng)新思維

根據(jù)筆者的科研經(jīng)歷，學習經(jīng)典問題的目的可能包含：①學習經(jīng)典問題的創(chuàng)新思想，豐富自己解決問題的工具箱（toolbox）；②現(xiàn)實中遇到的問題往往比經(jīng)典問題更加復雜（例如，電動車的路徑規(guī)劃、自動駕駛車的路徑規(guī)劃），需要針對這些問題的特征，對經(jīng)典問題的模型和算法進行二次創(chuàng)造；③將看似沒有關系的其他問題“轉(zhuǎn)化”為經(jīng)典問題，這需要對經(jīng)典問題有著深刻的理解。

針對我們的教學對象——交通類本科生，我們設計了多個應用舉例。

1）路面更新問題：道路路面每年的養(yǎng)護費用和階段性大修費用隨路面使用年限的增加而變化，需要決策在路面設計年限里的更新計劃，使得總費用最小。

2）火車售票處選址問題：現(xiàn)準備在七個居民點中設置一個售票處，已知各點之間的距離。問售票處設在哪個居民點，可使最大服務距離最??？若設置兩個售票處，應設在哪兩個居民點？

3）“全有全無”交通分配問題：已知某城市各交通小區(qū)之間的出行需求和路網(wǎng)（包括各條道路上的行程時間）。需要把這些出行需求按照行程時間最少的路徑（即全有全無）分配到路網(wǎng)各條道路上。

4）幾類限制條件下的最短路徑問題：如，找一條不通過某些邊的最短路徑，可對應于貨車限行、外牌通行、規(guī)避事故等情形下的路徑規(guī)劃。

需要指出的是，以上這些應用場景和應用舉例與學生后續(xù)的專業(yè)核心課程密切相關。當然，針對不同專業(yè)的學生，需要增強應用舉例問題場景的針對性，以提高學生的代入感、認同感以及與后續(xù)專業(yè)課的銜接性，培養(yǎng)學生的完整知識體系。

在課后作業(yè)的設計方面，除了Dijkstra算法本身的鞏固練習外，我們也設計了最短路徑應用問題建模方面的作業(yè)。

（四）? 程序?qū)崿F(xiàn)——綜合應用能力

我們在教學中引入“程序?qū)崿F(xiàn)”環(huán)節(jié)，引導學生從程序設計角度進一步理解最短路徑問題的求解原理，同時增強學生學以致用、善用計算機工具的綜合能力。據(jù)筆者了解，在許多專業(yè)的課程安排中，運籌學的課程學習節(jié)點往往處在通識基礎課與專業(yè)核心課的銜接段，加入“程序?qū)崿F(xiàn)”部分可更好地起到知識能力上的承前啟后作用，尤其是與計算機編程、數(shù)據(jù)結(jié)構(gòu)、算法設計等前序課程的銜接，以幫助學生搭建更為完整的知識體系。

我們的課程作業(yè)設計如下?；凇俺绦?qū)崿F(xiàn)”這個環(huán)節(jié)的教學設計，本教學團隊開設了運籌學實驗課。

考慮如圖2（a）所示的網(wǎng)絡，該網(wǎng)絡包括24個頂點、76條邊。各條邊的編號、尾節(jié)點、頭節(jié)點、長度和容量如數(shù)據(jù)表所示。請編程完成如下計算。

1）計算所有頂點對之間的最短路徑長度，并采用合適的圖表形式予以表達。

2）計算每一頂點到其他各頂點之間最短路徑長度的平均值，采用合適的圖表形式予以表達，并討論該結(jié)果反映了網(wǎng)絡中哪些信息。

3）計算每條邊被最短路徑使用的次數(shù)，并按照該次數(shù)對所有邊進行排序，討論該結(jié)果反映了網(wǎng)絡中哪些信息。

該課程作業(yè)不僅考察學生程序設計是否可以計算出正確的結(jié)果，還啟發(fā)學生選擇合適的圖表形式對計算結(jié)果予以可視化，增強計算和分析結(jié)果的可讀性。其中，第3個任務引導學生挖掘最短路徑信息所蘊含的豐富應用價值。一般而言，出行者偏好最短路徑或綜合考慮多個準則的最優(yōu)路徑。被多條最短路徑途經(jīng)的邊，可能是交通網(wǎng)絡中比較關鍵的邊。若失效，會使得途經(jīng)它們的多條最短路徑產(chǎn)生中斷，進而引發(fā)較為顯著的區(qū)域性、網(wǎng)絡化影響。

（五）? 算法比賽——團隊實戰(zhàn)積累

上述“程序?qū)崿F(xiàn)”環(huán)節(jié)的測試網(wǎng)絡較小，對學生的要求是“算得準”；“算法比賽”環(huán)節(jié)的測試網(wǎng)絡采用學生們所在的上海市道路網(wǎng)絡（網(wǎng)絡拓撲如圖2（b）所示），網(wǎng)絡規(guī)模巨大（18 277個節(jié)點，41 199個邊），貼近現(xiàn)實，對學生的要求是提高“算得準+算得快”的實戰(zhàn)能力。

該算法比賽以2～3人的小組為單位，在相同的實驗室計算機硬件配置條件下，比較計算時間以及對計算結(jié)果的挖掘程度。要求不僅能夠較為高效地得出最短路徑計算結(jié)果，還需要進一步挖掘計算結(jié)果所蘊含的多種應用價值。

三? 結(jié)束語

針對現(xiàn)有最短路徑問題教學中存在的“被動接受、手工計算、只算不用”等問題，我們結(jié)合教學實際，根據(jù)“精選算法、縱向到底、橫向到邊”的教學理念，探索出“算法原理—數(shù)學建?！獞门e例—程序?qū)崿F(xiàn)—算法比賽”五階遞進的最短路徑問題教學模式。2017—2022年的教學實踐結(jié)果表明，該教學模式有助于加深學生對最短路徑問題的理解認知，有利于提升學生的優(yōu)雅學術(shù)品位與實踐創(chuàng)新能力，教學效果得到較大的提升。

在未來的運籌學教學中，對于網(wǎng)絡規(guī)劃中的其他經(jīng)典問題，如最小生成樹、最大流、最小費用流等，均可根據(jù)問題自身特點與教學反饋，開展類似的多位一體教學設計，形成課堂內(nèi)外雙向促進，以更豐富完整、有趣有效的教學設計，提升教學質(zhì)量與學生綜合能力。此外，本文介紹的“應用舉例”主要針對我們授課的學生對象——交通工程和交通運輸類學生。針對不同專業(yè)的學生，可以引入相應的應用問題舉例，從而增強學生的專業(yè)意識，以及與后續(xù)專業(yè)課程的關聯(lián)度。

參考文獻：

[1] 傅家良.運籌學方法與模型[M].上海：復旦大學出版社，2014.

[2] 羅文昌.關于圖論教學的一些有益嘗試[J].大學數(shù)學，2014（30）：52-55.

[3] 李曉潔.基于問題導向教學的運籌學課程教學設計研究[J].高教學刊，2018（4）：101-107.

[4] 付云姍，劉蘭冬，劉奇鑫.關于運籌學教學方法的思考[J].科教文匯，2017（28）：40-41.

[5] 周喜華，胡振華，黃美銀，等.運籌學教學中融入數(shù)學建模實驗的研究和實踐[J].高教學刊，2017（11）：46-47.

[6] 姚翔飛，許鵬奎.教學研究型大學培養(yǎng)工科創(chuàng)新人才的實踐探索——基于學生創(chuàng)新能力提升的高校實踐教學體系改革與構(gòu)建[J].長春理工大學學報，2010，5（7）：1-2.

[7] DEO N， PANG C Y. Shortest-path algorithms： Taxonomy and annotation[J]. Networks， 2010，14（2）：275-323.