楊君子 張利民

[摘 要]最短路徑算法不僅具有重要的理論意義，而且具有重要的實用價值，它應用于交通運輸、設(shè)備更新、線路設(shè)計等各方面。本文介紹了Dijkstra算法，并針對衡水市某區(qū)域蔬菜農(nóng)產(chǎn)品配送到小區(qū)超市要求路線最短問題，建立數(shù)學模型給出最佳方案。

[關(guān)鍵詞]最短路徑;Dijkstra算法;農(nóng)產(chǎn)品

[中圖分類號]F326.6 [文獻標識碼]A

最短路問題是圖論中非常重要的最優(yōu)化問題之一，它是一個在現(xiàn)實生活中經(jīng)常被用到的基本工具，它可以解決現(xiàn)實生活中的許多實際問題，如城市中的管道鋪設(shè)、交通運輸、電子導航、線路安排、工廠布局、設(shè)備更新等。另外，它還可以解決最快路徑問題、最低費用問題、郵政選址問題等其他最優(yōu)化問題。最短路問題，一般來說就是從給定的網(wǎng)絡(luò)圖中找出任意兩點之間距離最短的一條路，就是從圖G中某對頂點vi和vj（i≠j）之間的所有路徑中權(quán)值之和最短的一條路徑作為頂點vi到頂點vj的最短路徑。

1 Dijkstra算法

Dijkstra算法是在一個賦權(quán)有向圖中能夠?qū)ふ页鲎疃搪穯栴}的最好方法，它是由荷蘭計算機科學家E.W.Dijkstra在1959年提出來的，它適用于所有弧的權(quán)值為非負的情況（即wij≥0）。Dijkstra算法在圖論中是一種典型的單源最短路徑算法，可以用來計算從一個給定的節(jié)點vs到其他所有點中任意一個點vj的最短路。Dijkstra算法的基本思想：從指定的點vs出發(fā)，逐漸一層一層向外擴充去尋找最短路。

2 農(nóng)產(chǎn)品配送最短路徑問題

由于農(nóng)產(chǎn)品中生鮮、鮮奶等時效性強，利用最短路徑算法解決配送的路線問題，以衡水市在某一個區(qū)域的農(nóng)產(chǎn)品運輸路線為研究背景，我們將對運輸流程做進一步的研究，首先將實際生活中復雜的地理線路簡單化，然后將利用最短路徑的逐次逼近法來優(yōu)化出最佳配送路線，使送貨員到達每個小區(qū)超市的路徑最短。

路線的選擇是衡水市桃城區(qū)的一個區(qū)域，在將現(xiàn)實問題平面化、虛擬化的過程中還應注意一些具體相關(guān)細節(jié)問題，考慮到現(xiàn)實與模型的差別和計算的方便以及一些其它因素，在此對現(xiàn)實情況的模型化做了如下的調(diào)整：①每條街道都想象成為直線，忽略現(xiàn)實兩個地點之間的道路是曲折的這一客觀因素;②一些胡同和小的路段忽略不計，只是標記出醒目的街道和路;③不考慮路線的車流量以及擁堵問題，通過每條路的各個條件都相同;④在運輸?shù)倪^程中不考慮經(jīng)過某個具體路段的時間要求，單純地考慮怎么樣規(guī)劃路程，使得送貨員在最后送到每個小區(qū)超市，所走的路線最短。

將現(xiàn)實道路虛擬化、模型化的過程：我們將日常生活中的實際問題轉(zhuǎn)化到我們的理論實踐當中，從圖論的角度考慮，為了使送貨員到達每個小區(qū)超市路程最短，將實際圖轉(zhuǎn)化為網(wǎng)絡(luò)圖，如下圖（兩個區(qū)域之間的距離單位為：m）：

v1代表鑫城嘉苑，v2代表恒豐理想城，v3代表桃城苑，v4代表華世鑫城，v5代表萬和苑，v6代表中央名邸，v7代表廣廈上城，v8代表中和盛景

在圖1的網(wǎng)絡(luò)圖中，各個節(jié)點代表各個小區(qū)的名稱，每條邊上的權(quán)值可以體現(xiàn)出能夠直接連通區(qū)域之間的距離。求出圖1所示的賦權(quán)有向圖D中從v1到各點的最短距離。設(shè)從任意一點vi到任意一點vj都有一條弧，如果沒有，則添加一條弧（vi， vj），并令wi=+∞，記Pj = P（vi， vj）為從v1到點vj的最短路長。

初始狀態(tài)：

第一次迭代：

同理可得：

第二次迭代：

（下轉(zhuǎn)頁）

（上接頁）

第三次迭代：

第四次迭代：

算法終止。由上面的推導過程可以得到送貨員到達每個小區(qū)超市的最短路徑為：。

在日常生活中，不管是路程最短還是時間最短、費用最短以及各種情況的選址問題等都可以應用最短路徑算法來解決。新的最短路徑算法的不斷出現(xiàn)與經(jīng)典的圖論、發(fā)展更加完善的計算機數(shù)據(jù)結(jié)構(gòu)以及算法的有效結(jié)合都是密不可分的。最短路徑問題仍是計算機科學、運籌學、交通工程學、地理信息學等學科的一個研究熱點。

[參考文獻]

[1] 胡運權(quán).運籌學教程[M].清華大學出版社，2012.

[2] 周維，楊鵬飛.運籌學[M].科學出版社，2008.

[3] 楊麗娟，劉渤海.基于Dijkstra拓展算法路線優(yōu)化[J].長春工業(yè)大學學報，2015（01）.

[4] 胡運權(quán).運籌學基礎(chǔ)及應用[M].高等教育出版社，2004（04）.