圖論最短路徑問(wèn)題

1、信息與管理科學(xué)學(xué)院信息與計(jì)算科學(xué)系課程論文課程名稱(chēng)： 圖與網(wǎng)絡(luò)優(yōu)化 論文名稱(chēng)： 圖論最短路徑問(wèn)題在消防選址中的應(yīng)用 僅供學(xué)習(xí)參考姓 名： 武冬冬 班 級(jí)： 12級(jí)金數(shù)二班 指導(dǎo)教師： 王亞偉 學(xué) 號(hào)： 1210110057 實(shí) 驗(yàn) 室： 信息管理實(shí)驗(yàn)室 日 期： 2021.06.06 圖論最短路徑問(wèn)題在消防選址中的應(yīng)用1210110057 武冬冬【摘 要】 最短路問(wèn)題是一類(lèi)重要的優(yōu)化問(wèn)題，它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際中的許多問(wèn)題，如管道鋪設(shè)、線(xiàn)路安排、廠(chǎng)區(qū)布局、設(shè)備更新等，而且還經(jīng)常作為一個(gè)根本工具，用于解決其他優(yōu)化問(wèn)題。本文介紹了圖論最短路徑問(wèn)題及其算法，并應(yīng)用圖論最短路徑問(wèn)題的分析方法

2、，解決城市消防站的選址問(wèn)題?！娟P(guān)鍵詞】 最短路徑；Dijkstra算法；消防選址1 引言圖論是運(yùn)籌學(xué)的一個(gè)重要分支，旨在解決離散型的優(yōu)化問(wèn)題，近年來(lái)開(kāi)展十分迅速。在人們的社會(huì)實(shí)踐中，圖論已成為解決自然科學(xué)、工程技術(shù)、社會(huì)科學(xué)、生物技術(shù)以及經(jīng)濟(jì)、軍事等領(lǐng)域中許多問(wèn)題的有力工具之一。圖論中的“圖，并不是通常意義下的幾何圖形或物體的形狀圖，也不是工程設(shè)計(jì)圖中的“圖，而是以一種抽象的形式來(lái)表達(dá)一些確定的對(duì)象，以及這些對(duì)象之間具有或不具有某種特定關(guān)系的一個(gè)數(shù)學(xué)系統(tǒng)。也就是說(shuō)，幾何圖形是表述物體的形狀和結(jié)構(gòu)，圖論中的“圖那么描述一些特定的事物和這些事物之間的聯(lián)系。它是數(shù)學(xué)中經(jīng)常采用的抽象直觀(guān)思維方法的典型

3、代表。2 圖論根本概念2.1 圖的定義有序三元組稱(chēng)為一個(gè)圖，其中：(1)是有窮非空集，稱(chēng)為頂點(diǎn)集，其元素叫做圖的頂點(diǎn)；(2)稱(chēng)為邊集，其元素叫做圖的邊；(3)是從邊集到頂點(diǎn)集的有序或者無(wú)序?qū)系挠吧洌Q(chēng)為關(guān)聯(lián)函數(shù)。2.2 圖的分類(lèi)在圖中，與中的有序偶對(duì)應(yīng)的邊稱(chēng)為圖的有向邊(或弧)，而與中頂點(diǎn)的無(wú)序偶對(duì)應(yīng)的邊稱(chēng)為圖形的無(wú)向邊，每一條邊都是無(wú)向邊的圖，叫做無(wú)向圖，記為；每一條邊都是有向邊的圖叫做有向圖，記為；既有無(wú)向邊又有有向邊的圖叫做混合圖。2.3 權(quán)如果圖中任意一條邊上都附有一個(gè)數(shù)，那么稱(chēng)這樣的圖為賦權(quán)圖，稱(chēng)為邊上的權(quán)。3 最短路徑問(wèn)題最短路徑問(wèn)題是圖論中的一個(gè)根本問(wèn)題。在賦權(quán)圖中，每條邊都

4、有一個(gè)數(shù)值(長(zhǎng)度、本錢(qián)、時(shí)間等)，找出兩節(jié)點(diǎn)之間總權(quán)和最小的路徑就是最短路徑問(wèn)題。最短路徑問(wèn)題，通常歸屬為三類(lèi)：(1)單源最短路徑問(wèn)題：包括確定起點(diǎn)的最短路徑問(wèn)題和確定終點(diǎn)的最短路徑問(wèn)題。確定終點(diǎn)與確定起點(diǎn)的最短路徑問(wèn)題相反，該問(wèn)題是終點(diǎn)，求最短路徑問(wèn)題。在無(wú)向圖中該問(wèn)題與確定起點(diǎn)的問(wèn)題完全等同，在有向圖中該問(wèn)題等同于把所有路徑方向反轉(zhuǎn)確實(shí)定起點(diǎn)的問(wèn)題。(2)確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題：即起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。(3)全局最短路徑問(wèn)題：求圖中所有的最短路徑。4 最短路徑算法在賦權(quán)圖中尋求最短路的算法通常有兩種：Dijkstra算法和Floyd算法。4.1 Dijkstra算法當(dāng)所有

5、的權(quán)數(shù)時(shí)，Dijkstra算法是目前公認(rèn)的最好的算法。其根本思想是從起點(diǎn)出發(fā)，逐步向外開(kāi)展。探索過(guò)程中，每到一個(gè)點(diǎn)，都記錄下路徑與路程，稱(chēng)為這個(gè)點(diǎn)的標(biāo)號(hào)。故Dijkstra算法也稱(chēng)為標(biāo)號(hào)法。具體標(biāo)號(hào)由兩局部構(gòu)成，第一局部是一個(gè)字母，表示前面的一個(gè)點(diǎn)的符號(hào)，說(shuō)明從哪里來(lái)；第二局部是一個(gè)數(shù)字，表示從起點(diǎn)到目前位置的距離，說(shuō)明有多遠(yuǎn)。標(biāo)號(hào)被分成臨時(shí)標(biāo)號(hào)和永久標(biāo)號(hào)兩種。前者是可以修改的，后者是不變的。開(kāi)始的時(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)過(guò)次，可以求出從起點(diǎn)到終點(diǎn)的最短路徑和路程。Dijkstra的算法步驟為：設(shè)起點(diǎn)為，終點(diǎn)為。(1) 起

6、點(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.2 Floyd算法在某些問(wèn)題中，需要確定圖中任意兩點(diǎn)之間的最短路徑與路程。如采用Dijkstra算法求解，那么須依次變換起點(diǎn)，重復(fù)執(zhí)行算法次才能得到所需結(jié)果，這顯然過(guò)于繁瑣。Floyd算法可以借助于權(quán)矩陣直接求出任意兩點(diǎn)之間的最短路徑。首先定義賦權(quán)圖的權(quán)矩陣：這里 式中，表示的權(quán)數(shù)。Floyd的算法步驟：(1)令，輸人權(quán)矩陣。(2)令，計(jì)算 ，式中。(3)如果，終止算法；否那么，返回步驟(2)

7、。上述算法的最終結(jié)果中元素就是從頂點(diǎn)到的最短路程。如果希望計(jì)算結(jié)果不僅給出任意兩點(diǎn)間的最短路程，而且給出具體的最短路徑，那么在運(yùn)算過(guò)程中要保存下標(biāo)的信息，即。5 最短路徑問(wèn)題在消防站選址中的應(yīng)用某城市的開(kāi)發(fā)區(qū)中要建一個(gè)消防站，該開(kāi)發(fā)區(qū)的示意圖如圖1所示，其中表示開(kāi)發(fā)區(qū)中10個(gè)消防重點(diǎn)單位，考慮到交通路況，局部單位之間往返的距離不完全相同，分析消防站選址問(wè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ù)稱(chēng)為頂點(diǎn)的最大效勞距離，記做。要使消防車(chē)到達(dá)各個(gè)點(diǎn)的距離盡可能

8、的短，應(yīng)選取最大效勞距離最小的點(diǎn)，即。圖l的權(quán)矩陣為： 用Floyd算法進(jìn)行計(jì)算，得到各個(gè)節(jié)點(diǎn)之間的最短距離如表l，其中任意兩頂點(diǎn)的最短路線(xiàn)如表2。 表1： 各節(jié)點(diǎn)之間的最短距離1234567891010539510119131425024499811123320627861011461305756785542805648961097106052787106755201238986341305691289774230510139108853450表2：任意兩個(gè)頂點(diǎn)的最短路線(xiàn)i j123451l一32l一3l一324l一352231232423533一l32324354423一l42423423

9、5553一l532535324663一l63一263687468577853一l7427853747858853一l8352853874859978531974297853974978510107853110742107853107410785i j6789101l一36l一357l一358l一35791一35710223624723582469247一lO335863573583579357一10447864747847947105586575857957一106687686879687一10778678797一108868787987一lO997869797897一lO101078610710781079由表1可知：， ， ， ， ， ， ， ， 其中點(diǎn)具有最小的最大效勞距離，所以把消防隊(duì)建在最合