版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
若干補充
11.Floyd算法在以下情況可以簡化:(1)如有度數(shù)為1的端,可把它們?nèi)サ粼僮鲇嬎?設(shè)為度數(shù)為1的端,它只與相連,則與其它端的最短徑必經(jīng),所以2(2)如有度數(shù)為2的端,則按下述方法去掉:設(shè)為度數(shù)為2的端,它只與相連,若,則可簡單地去掉若,也可去掉,但把改成
3不論那種情況,與其它端間的最短徑長用下述公式計算:(3)稀疏網(wǎng)的情況下可把全圖分成幾個部分來計算,然后合并.當(dāng)網(wǎng)的邊數(shù)遠少于全聯(lián)網(wǎng)的邊數(shù)時,稱稀疏網(wǎng).此時往往存在割端或端數(shù)較少的割端.對于有割端的網(wǎng)G,去掉后就把G分成幾部分(例如三部分G1,G2,G3),用Floyd算法分別求出的最短距離陣及路由陣.若則間最短距離為4例567892.次短徑和可用徑:若兩端間有幾條徑,其中P1為最短徑,而P2與P1無公共邊卻有公共端,則稱P2不共邊徑或邊分離徑;若P3與P1除起終點外無公共端(必?zé)o公共邊),則稱P3為不共端徑或端分離徑.求次短徑的方法1)對不共邊徑從圖中去掉最短徑的所有邊,然后在剩下的圖中求最短徑;2)對不共端徑從圖中去掉最短徑的所有中間端(當(dāng)然段的關(guān)聯(lián)邊也去掉),然后在剩下的圖中求最短徑;10這個過程還可繼續(xù)下去.例:11從到有三條徑:12邊分離的次短徑13端分離的次短徑14可用徑在某些應(yīng)用中,要求找一批滿足條件的徑.當(dāng)有幾個條件時,可先用一個條件求可用徑,再在其中篩選出滿足其它條件的可用徑.今用限制條件為徑長的例子來說明算法:仍用上圖,要求徑的長度小于M(=7)的可用徑.1)用F算法求出圖的最短徑長矩陣W和轉(zhuǎn)接矩陣R;2)若,則無可用徑,
若,則找一個的鄰接節(jié)點,如果則排除,否則就得一可用徑15本例的距離矩陣,最短路徑和轉(zhuǎn)接矩陣分別如下16是可用徑.再看V1與V3能否延續(xù)17與V1相連的有V2,與V3相連的有V2.與V2相連的有V4.18193.圖的中心和中點從端間最短距離出發(fā)可定義網(wǎng)的中心,中點和直徑一個端在網(wǎng)內(nèi)的位置可用最長的最短徑表示:
的最小值所對應(yīng)的端定義為網(wǎng)的中心:網(wǎng)的中點可定義為平均最短徑長最小的端:20網(wǎng)的直徑:例21
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年度甘肅省安全員之A證(企業(yè)負責(zé)人)全真模擬考試試卷B卷含答案
- 2024年毛發(fā)化學(xué)品:洗發(fā)精合作協(xié)議書
- 簡單的頂房合同(2篇)
- 鋼鐵廠續(xù)簽合同(2篇)
- 2024年非鐵分選提純設(shè)備項目發(fā)展計劃
- 2024年自配合組合電器項目建議書
- 2024年辦公商業(yè)空間設(shè)計項目發(fā)展計劃
- 高效快遞運輸線路外包合同
- 2024版合同-民事合同
- 2024版合同服務(wù)項目合同合同創(chuàng)新報告
- IATF16949-2024質(zhì)量管理體系各過程風(fēng)險識別評價分析及控制方案
- 河北衡水中學(xué)2024-2025學(xué)年高二年級上學(xué)期綜合素質(zhì)評價地理試題含解析
- 服務(wù)行業(yè)感受心得體會(8篇)
- 滬科版九年級物理 15.1 電阻和變阻器(學(xué)習(xí)、上課課件)
- 鋁渣資源化的綠色之路-推動鋁冶煉行業(yè)可持續(xù)發(fā)展
- 《長征勝利萬歲》課件(33張)2024-2025學(xué)年高中語文統(tǒng)編版選擇性必修上冊第一單元
- 2023年中國人壽保險股份有限公司招聘筆試真題
- 2024年口服美容市場趨勢白皮書
- 2024-2025學(xué)年人教版數(shù)學(xué)九年級上冊第一次月考試題
- 合肥供電公司城市新建住宅小區(qū)電力建設(shè)技術(shù)標(biāo)準
- 滬教版2024九年級上冊化學(xué)各章節(jié)必背知識點復(fù)習(xí)提綱
評論
0/150
提交評論