王秋薈+陳繼斌

摘要：隨著科學技術的發(fā)展，最短路問題在生活中應用得越來越廣泛，所以研究最短路徑問題有非常的重要意義。通過對Dijkstra、Floyd兩種最短路算法進行圖示解析，能讓我們更好地理解算法思想以及求最短路徑的過程，進而將其應用在實際工程的優(yōu)化設計中。

關鍵詞：最短路徑；Di]kstra算法；Flovd算法

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2017）17-0240-02

1概述

最短路徑問題在網絡理論中應用得比較廣泛，許多問題的優(yōu)化，如廠區(qū)選址、火災救援、交通運輸、管道敷設、線路安排等都可轉化為最短路徑問題來處理。兩點之間的最短路徑就是兩點間的所有路徑中邊的權值之和為最小的路徑，而不是經過邊的數目最少的路徑。

2 Dijkstra算法

Dijkstra算法的前提條件是整個網絡拓撲圖，用圖中的頂點表示地點，每一條邊旁的數字稱為權值，權值可以表示費用、距離等，這種算法只適用于求無負權網絡圖的最短路徑；我們結合圖1來介紹Dijkstra算法，圖中我們要求源點V0到其他任意頂點的最短路徑；

4最短路徑算法在線路敷設中的應用

線路敷設是建筑工程施工設計中重要的部分，我們通過對敷設線路的優(yōu)化來達到降低成本、增加可靠性的目的。線路設計的目標是在滿足工程要求又符合規(guī)范的基礎上減少用線纜量，其實這就是一個對線纜走向進行優(yōu)化設計的問題，故如果我們將工程中需要接線的設備設為網絡圖的各頂點，設備到設備之間的路線設為無向圖的邊，這樣線路的敷設問題就轉化為了最短路徑問題，進而我們就可以用最短路徑算法找出網絡圖中最短又合理的路徑來實現線路的優(yōu)化。我們可以用以上的三種算法，根據其處理速度和準確性的比較來選擇一種更優(yōu)的算法。

5結束語

Dijkstra算法和Bellman-ford算法都是求圖中源點到其他所有頂點之間最短路徑算法，Dijkstra算法求的是單源以及無負權網絡圖的最短路徑，Bellman-ford算法可以求有負權網絡圖的最短路徑，這種算法可以判斷是否有負權回路；Dijkstra算法在計算過程中，源點到頂點集S里各頂點的最短路徑長度不再改變，改變的只是源點到不在頂點集S里各頂點的最短路徑，而Bellman-ford算法在計算過程中，每次循環(huán)都要計算源點到各頂點的最短路徑長度，直到Bellman-ford算法結束才確定。