Floyd算法及其軟件實(shí)現(xiàn)課件

任意兩點(diǎn)間的最短路問題Floyd算法使用范圍:求每對(duì)頂點(diǎn)的最短路徑;有向圖、無向圖和混合圖;算法思想:

直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次遞推地構(gòu)造出n個(gè)矩陣D(1),D(2),…,D(v),D(v)是圖的距離矩陣,同時(shí)引入一個(gè)后繼點(diǎn)矩陣記錄兩點(diǎn)間的最短路徑.輸入?yún)?shù)：G的帶權(quán)鄰接矩陣W.算法輸出：距離矩陣D以及路由矩陣R.Floyd算法及其軟件實(shí)現(xiàn)（I）求距離矩陣的方法.Floyd算法及其軟件實(shí)現(xiàn)（II）求路徑矩陣的方法.在建立距離矩陣的同時(shí)可建立路徑矩陣R．（III）查找最短路路徑的方法.然后用同樣的方法再分頭查找．若：（IV）Floyd算法：求任意兩頂點(diǎn)間的最短路.例3：求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑.Floyd算法及其軟件實(shí)現(xiàn)插入點(diǎn)v1，得：矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素.Floyd算法及其軟件實(shí)現(xiàn)插入點(diǎn)v2，得：矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素.Floyd算法及其軟件實(shí)現(xiàn)插入點(diǎn)v3，得：插入點(diǎn)v4，得：插入點(diǎn)v5，得：Floyd算法及其軟件實(shí)現(xiàn)插入點(diǎn)v6，得：Floyd算法及其軟件實(shí)現(xiàn)故從v5到v2的最短路為8由v6向v5追溯:由v6向v2追溯:所以從到的最短路徑為：Floyd算法及其軟件實(shí)現(xiàn)選址問題1、中心問題所謂中心選址問題就是在一網(wǎng)絡(luò)中選擇一點(diǎn)，建立公用服務(wù)設(shè)施，為該網(wǎng)絡(luò)中的點(diǎn)提供服務(wù)，使得服務(wù)效率最高。比如一個(gè)區(qū)域的消防站、自來水廠、學(xué)校、變電站、銀行、商店等選址。為了提高服務(wù)效率，自然的想法是將這些設(shè)施建立在中心地點(diǎn)。要求網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點(diǎn)離服務(wù)設(shè)施的距離盡可能小。Floyd算法及其軟件實(shí)現(xiàn)設(shè)網(wǎng)絡(luò)N有個(gè)n點(diǎn)v1,v2,…,vn。dij表示點(diǎn)vi到vj之間的距離（即最短路的長度），并記dii=0(i=1,2,…,n)。定義1:

記,。若,則稱點(diǎn)vk為網(wǎng)絡(luò)N的中心，I為直徑。定義2:

令，若，則稱vk為網(wǎng)絡(luò)N的中心。Floyd算法及其軟件實(shí)現(xiàn)例1某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示．問應(yīng)設(shè)在哪個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短。Floyd算法及其軟件實(shí)現(xiàn)S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處.Floyd算法及其軟件實(shí)現(xiàn)例2教育部門打算在某新建城區(qū)建一所學(xué)校，讓附近七個(gè)居民區(qū)的學(xué)生就近入學(xué)。七個(gè)居民區(qū)之間的道路如下圖所示，學(xué)校應(yīng)建在哪個(gè)居民區(qū)，才能使大家都方便？（圖中距離單位：百米）。Floyd算法及其軟件實(shí)現(xiàn)Floyd算法及其軟件實(shí)現(xiàn)Floyd算法及其軟件實(shí)現(xiàn)2、重心問題Floyd算法及其軟件實(shí)現(xiàn)例3例2中，七個(gè)居民區(qū)的學(xué)生人數(shù)分別為：40、25、45、30、20、35、50人，學(xué)校應(yīng)建在哪個(gè)居民區(qū)，才能使大家都方便？（圖中距離單位：百米）。Floyd算法及其軟件實(shí)現(xiàn)Floyd算法及其軟件實(shí)現(xiàn)簡易公路建設(shè)方案

某合同戰(zhàn)術(shù)訓(xùn)練基地為保障即將進(jìn)行的聯(lián)合軍事演習(xí)，準(zhǔn)備在原有的1個(gè)油庫的基礎(chǔ)上，再設(shè)立7個(gè)固定的燃料補(bǔ)給點(diǎn)。練習(xí)Floyd算法及其軟件實(shí)現(xiàn)v1v7v6v2v8v5v3v4油庫與補(bǔ)給點(diǎn)的位置如圖所示，其中油庫位于v1點(diǎn)，補(bǔ)給點(diǎn)位于v2,…,v8點(diǎn)。Floyd算法及其軟件實(shí)現(xiàn)經(jīng)過前期的測繪工作，如果在油庫和補(bǔ)給點(diǎn)之間修建簡易公路，由于地形不同，每段公路花費(fèi)如圖，每單位費(fèi)用為1萬元。請根據(jù)測繪結(jié)果，規(guī)劃一個(gè)總造價(jià)最低的建設(shè)方案。v1v7v6v2v8v