導航:首頁 > 源碼編譯 > 圖上兩點之間最短距離演算法

圖上兩點之間最短距離演算法

發布時間:2024-01-19 04:05:33

A. 弗洛伊德演算法求出最短距離

(1)利用二維數組dist[i][j]記錄當前vi到vj的最短路徑長度,數組dist的初值等於圖的帶權鄰接矩陣;


(3)依次向S中加入v0,v1…vn-1,每加入一個頂點,對dist[i][j]進行一次修正:設S={v0,v1…vk-1},加入vk,則dist(k)[i][j]=min{dist(k-1)[i][j],dist(k-1)[i][k]+dist(k-1)[k][j]}。

dist(k)[i][j]的含義:允許中間頂點的序號最大為k時從vi到vj的最短路徑長度。
dist(n-1)[i][j]就是vi到vj的最短路徑長度。

弗洛伊德最短距離演算法(FloydShortestPathAlgorithm)又稱為插點法,是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的演算法。該演算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。
中文名弗洛伊德最短距離演算法
外文名FloydShortestPathAlgorithm
所屬學科IT
所屬領域程序設計
簡介
最短路問題是網路最優化中一個基本而又非常重要的問題,這一問題相對比較簡單,在實際生產和生活中經常遇到,許多的網路最優化問題可以化為最短路問題,或者用最短路演算法作為其子程序.因此,最短路的用途已遠遠超出其表面意義迄今為止,所有最短路演算法都只對不含負迴路的網路有效,實際上對含有負迴路的網路,其最短路問題是NP困難的,因此本研究所討論的網路也不含負迴路.此外,如果將無向圖每條邊用兩條端點相同、方向相反的弧來代替,可以將其化為有向圖,因而不討論無向圖.本研究中未述及的術語、記號。
Floyd演算法是一種用於尋找給定加權圖中頂點間最短路徑的演算法,以1978年圖靈獎獲得者斯坦福大學計算機科學系教授RobertW.Floyd命名。Floyd演算法採用動態規劃的原理計算兩兩頂點間最短路徑,主要解決網路路由尋找最優路徑的問題。

閱讀全文

與圖上兩點之間最短距離演算法相關的資料

熱點內容
php讀取二維數組 瀏覽:348
php編譯安裝參數 瀏覽:278
其實壓力沒那麼大程序員圖片 瀏覽:416
如何查看app內訪問的網頁地址 瀏覽:757
安卓手機信號旁邊的漢字怎麼設置 瀏覽:304
nrf2401單片機 瀏覽:713
清除電腦文件夾垃圾的方法 瀏覽:226
天河程序員 瀏覽:192
成都程序員公積金 瀏覽:768
程序員為什麼叫程序猿 瀏覽:484
加西貝拉壓縮機價格 瀏覽:787
海信聚好看如何用u盤安裝app 瀏覽:71
加密狗怎麼寫的 瀏覽:560
安卓手機如何能調最大聲音 瀏覽:668
編程開發工具大全 瀏覽:572
如何把安卓系統換成windows 瀏覽:31
android拼接url 瀏覽:25
華為nfc復制加密卡怎麼模擬 瀏覽:775
在pdf中怎麼插入文件 瀏覽:115
單片機中fw縮寫是什麼 瀏覽:378