圖論中最短路徑問題

《圖論中最短路徑問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、圖論最短路徑問題在消防選址中的應(yīng)用【摘要】最短路徑問題是圖論解決的典型實(shí)際問題之一，可用來解決管路鋪設(shè)、線路安裝、廠區(qū)布局和設(shè)備更新等實(shí)際問題。介紹了圖論最短路徑問題及其算法，并應(yīng)用圖論最短路徑問題的分析方法，解決城市消防站的選址問題?！娟P(guān)鍵詞】最短路徑；Floyd算法；消防1引言圖論是運(yùn)籌學(xué)的一個(gè)重要分支，旨在解決離散型的優(yōu)化問題，近年來發(fā)展十分迅速。在人們的社會(huì)實(shí)踐中，圖論已成為解決自然科學(xué)、工程技術(shù)、社會(huì)科學(xué)、生物技術(shù)以及經(jīng)濟(jì)、軍事等領(lǐng)域中許多問題的有力工具之一。圖論中的“圖”，并不是通常意義下的幾何圖形或物體的形狀圖，也不是工程設(shè)計(jì)圖中的“圖

2、”，而是以一種抽象的形式來表達(dá)一些確定的對(duì)象，以及這些對(duì)象之間具有或不具有某種特定關(guān)系的一個(gè)數(shù)學(xué)系統(tǒng)。也就是說，幾何圖形是表述物體的形狀和結(jié)構(gòu)，圖論中的“圖”則描述一些特定的事物和這些事物之間的聯(lián)系。它是數(shù)學(xué)中經(jīng)常采用的抽象直觀思維方法的典型代表。2圖論基本概念2.1圖的定義有序三元組稱為一個(gè)圖，其中：(1)是有窮非空集，稱為頂點(diǎn)集，其元素叫做圖的頂點(diǎn)；(2)稱為邊集，其元素叫做圖的邊；(3)是從邊集到頂點(diǎn)集的有序或者無序?qū)系挠吧?，稱為關(guān)聯(lián)函數(shù)。2.2圖的分類在圖中，與中的有序偶對(duì)應(yīng)的邊稱為圖的有向邊(或弧)，而與中頂點(diǎn)的無序偶對(duì)應(yīng)的邊稱為圖形的

3、無向邊，每一條邊都是無向邊的圖，叫做無向圖，記為；每一條邊都是有向邊的圖叫做有向圖，記為；既有無向邊又有有向邊的圖叫做混合圖。2.3權(quán)如果圖中任意一條邊上都附有一個(gè)數(shù)，則稱這樣的圖為賦權(quán)圖，稱為邊上的權(quán)。43最短路徑問題最短路徑問題是圖論中的一個(gè)基本問題。在賦權(quán)圖中，每條邊都有一個(gè)數(shù)值(長(zhǎng)度、成本、時(shí)間等)，找出兩節(jié)點(diǎn)之間總權(quán)和最小的路徑就是最短路徑問題。最短路徑問題，通常歸屬為三類：(1)單源最短路徑問題：包括確定起點(diǎn)的最短路徑問題和確定終點(diǎn)的最短路徑問題。確定終點(diǎn)與確定起點(diǎn)的最短路徑問題相反，該問題是已知終點(diǎn)，求最短路徑問題。在無向圖中該問題與確

4、定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。(2)確定起點(diǎn)終點(diǎn)的最短路徑問題：即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。(3)全局最短路徑問題：求圖中所有的最短路徑。4最短路徑算法在賦權(quán)圖中尋求最短路的算法通常有兩種：Dijkstra算法和Floyd算法。4.1Dijkstra算法當(dāng)所有的權(quán)數(shù)時(shí)，Dijkstra算法是目前公認(rèn)的最好的算法。其基本思想是從起點(diǎn)出發(fā)，逐步向外發(fā)展。探索過程中，每到一個(gè)點(diǎn)，都記錄下路徑與路程，稱為這個(gè)點(diǎn)的標(biāo)號(hào)。故Dijkstra算法也稱為標(biāo)號(hào)法。具體標(biāo)號(hào)由兩部分構(gòu)成，第一部分是一個(gè)字母，

5、表示前面的一個(gè)點(diǎn)的符號(hào)，說明從哪里來；第二部分是一個(gè)數(shù)字，表示從起點(diǎn)到目前位置的距離，說明有多遠(yuǎn)。標(biāo)號(hào)被分成臨時(shí)標(biāo)號(hào)和永久標(biāo)號(hào)兩種。前者是可以修改的，后者是不變的。開始的時(shí)候，所有的標(biāo)號(hào)都是臨時(shí)標(biāo)號(hào)，每一次算法循環(huán)，將其中的某一個(gè)臨時(shí)標(biāo)號(hào)改變?yōu)橛谰脴?biāo)號(hào)。因此，最多經(jīng)過次，可以求出從起點(diǎn)到終點(diǎn)的最短路徑和路程。Dijkstra的算法步驟為：設(shè)起點(diǎn)為，終點(diǎn)為。(1)起點(diǎn)標(biāo)號(hào)(一，0)，鄰點(diǎn)標(biāo)號(hào)，其他標(biāo)號(hào)。令。(2)如果，終止算法。(3)選擇，具有最小標(biāo)號(hào)。如果，終止算法；否則，將的標(biāo)號(hào)改成永久標(biāo)號(hào)，令。(4)檢查的鄰點(diǎn)，如果，則給標(biāo)號(hào)并返回步驟(2)。4

6、.2Floyd算法在某些問題中，需要確定圖中任意兩點(diǎn)之間的最短路徑與路程。如采用Dijkstra算法求解，則須依次變換起點(diǎn)，重復(fù)執(zhí)行算法次才能得到所需結(jié)果，這顯然過于繁瑣。Floyd算法可以借助于權(quán)矩陣直接求出任意兩點(diǎn)之間的最短路徑。首先定義賦權(quán)圖的權(quán)矩陣：這里4式中，表示的權(quán)數(shù)。Floyd的算法步驟：(1)令，輸人權(quán)矩陣。(2)令，計(jì)算，式中。(3)如果，終止算法；否則，返回步驟(2)。上述算法的最終結(jié)果中元素就是從頂點(diǎn)到的最短路程。如果希望計(jì)算結(jié)果不僅給出任意兩點(diǎn)間的最短路程，而且給出具體的最短路徑，則在運(yùn)算過程中要保留下標(biāo)的信息，即。5最短路徑

7、問題在消防站選址中的應(yīng)用某城市的開發(fā)區(qū)中要建一個(gè)消防站，該開發(fā)區(qū)的示意圖如圖1所示，其中表示開發(fā)區(qū)中10個(gè)消防重點(diǎn)單位，考慮到交通路況，部分單位之間往返的距離不完全相同，分析消防站選址問題。消防站選址應(yīng)該遵循到達(dá)各個(gè)點(diǎn)的距離盡可能短的原則為最好，這樣才能做到在火災(zāi)發(fā)生時(shí)盡快趕到火災(zāi)現(xiàn)場(chǎng)而不延誤滅火時(shí)機(jī)。在圖1中任取一點(diǎn)，考慮與中其他頂點(diǎn)間的距離，把這個(gè)距離中最大數(shù)稱為頂點(diǎn)的最大服務(wù)距離，記做。要使消防車到達(dá)各個(gè)點(diǎn)的距離盡可能的短，應(yīng)選取最大服務(wù)距離最小的點(diǎn)，即。圖l的權(quán)矩陣為：4用Floyd算法進(jìn)行計(jì)算，得到各個(gè)節(jié)點(diǎn)之間的最短距離如表l，其中任意兩頂

8、點(diǎn)的最短路線如表2。表1：各節(jié)點(diǎn)之間的最短距離1234567891010539510119131425024