最短路徑算法的圖示解析

王秋薈+陳繼斌

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

關(guān)鍵詞：最短路徑；Di]kstra算法；Flovd算法

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）17-0240-02

1概述

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

2 Dijkstra算法

Dijkstra算法的前提條件是整個(gè)網(wǎng)絡(luò)拓?fù)鋱D，用圖中的頂點(diǎn)表示地點(diǎn)，每一條邊旁的數(shù)字稱為權(quán)值，權(quán)值可以表示費(fèi)用、距離等，這種算法只適用于求無負(fù)權(quán)網(wǎng)絡(luò)圖的最短路徑；我們結(jié)合圖1來介紹Dijkstra算法，圖中我們要求源點(diǎn)V0到其他任意頂點(diǎn)的最短路徑；

4最短路徑算法在線路敷設(shè)中的應(yīng)用

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

5結(jié)束語

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