導航:首頁 > 源碼編譯 > 圖論頂點間路徑長度演算法

圖論頂點間路徑長度演算法

發布時間:2024-11-07 23:58:52

① 求有向圖兩個頂點間的最短路徑的方法,用簡單語言或舉例描述。

在交通網路中,常常會提出許多這樣的問題:兩地之間是否有路相通?在有多條通路的情況下,哪一條最近?哪一條花費最少等。交通網路可以用帶權圖表示,圖中頂點表示域鎮,邊表示兩城之間的道路,邊上權值可表示兩城鎮間的距離,交通費用或途中所需的時間等。
以上提出的問題就是帶權圖中求最短路徑的問題,即求兩個頂點間長度最短的路徑。
最短路徑問題的提法很多。在這里僅討論單源最短路徑問題:即已知有向圖(帶權),我們希望找出從某個源點S∈V到G中其餘各頂點的最短路徑。
例如:下圖(有向圖G14),假定以v1為源點,則其它各頂點的最短路徑如下表所示:

圖 G14

從有向圖可看出,頂點v1到v4的路徑有3條:(v1,v2,v4),(v1,v4),(v1,v3,v2,v4 ),其路徑長度分別為:15,20和10。因此v1到v4的最短路徑為(v1,v3,v2,v4 )。
為了敘述方便,我們把路徑上的開始點稱為源點,路徑的最後一個頂點為終點。
那麼,如何求得給定有向圖的單源最短路徑呢?迪傑斯特拉(Dijkstra)提出按路徑長度遞增產生諸頂點的最短路徑演算法,稱之為迪傑斯特拉演算法。
迪傑斯特拉演算法求最短路徑的實現思想是:設有向圖G=(V,E),其中,V={1,2,…,n},cost是表示G的鄰接矩陣,cost[i][j] 表示有向邊<i,j>的權。若不存在有向邊<i,j>,則cost[i][j]的權為無窮大(這里取值為32767)。設S是一個集合,其中的每個元素表示一個頂點,從源點到這些頂點的最短距離已經求出。設頂點v1為源點,集合S的初態只包含頂點v1。數組dist記錄從源點到其他各頂點當前的最短距離,其初值為dist[i]=cost[v1][i],i=2,…,n。從S之外的頂點集合V-S 中選出一個頂點w,使dist[w]的值最小。於是從源點到達w只通過S 中的頂點,把w加入集合S中調整dist中記錄的從源點到V-S中每個頂點v的距離:從原來的dist[v] 和dist[w]+cost[w][v]中選擇較小的值作為新的dist[v]。重復上述過程,直到S中包含V中其餘頂點的最短路徑。
最終結果是:S記錄了從源點到該頂點存在最短路徑的頂點集合,數組dist記錄了從源點到 V中其餘各頂點之間的最短路徑,path是最短路徑的路徑數組,其中path[i] 表示從源點到頂點i之間的最短路徑的前驅頂點。

閱讀全文

與圖論頂點間路徑長度演算法相關的資料

熱點內容
建立個文件夾就帶個鎖頭 瀏覽:658
android獲取手機硬體 瀏覽:138
華為伺服器ge是什麼意思 瀏覽:842
微鉑加密 瀏覽:177
劍橋發加密郵件 瀏覽:708
linux查看文檔命令 瀏覽:299
雲伺服器java插件 瀏覽:182
安卓手機怎麼記錄吸煙 瀏覽:484
如何找郵件伺服器 瀏覽:750
內核編譯到一半提示空間不足 瀏覽:873
新形勢下結演算法 瀏覽:571
bgp機房是否高於雲伺服器機房 瀏覽:634
安卓系統聊天記錄怎麼找 瀏覽:852
php地址傳值 瀏覽:675
成考本科程序員公司承認嗎 瀏覽:663
mc伺服器怎麼取消我的夥伴 瀏覽:322
lua為什麼需要編譯 瀏覽:83
mac轉pdf 瀏覽:967
百度文件怎麼解壓縮密碼 瀏覽:295
調用編譯器後運行程序段 瀏覽:1000