最小生成樹and最短路徑-資料下載頁(yè)
2025-06-23 18:52本頁(yè)面
【正文】 103明顯結(jié)點(diǎn)3到源點(diǎn)的最短路徑已定，則結(jié)點(diǎn)3也在S集合中，dist[3]被賦值為10。1S加入結(jié)點(diǎn)3后，特殊路徑有{11113135}，最短特殊路徑為1355 103 1明顯結(jié)點(diǎn)5到源點(diǎn)的最短路徑已定，則結(jié)點(diǎn)5也在S集合中，dist[5]被賦值為11。以此類推，直到所有的點(diǎn)的dist被計(jì)算出來(lái)。難點(diǎn)無(wú)論是邊集數(shù)組還是鄰接矩陣來(lái)存儲(chǔ)圖，對(duì)迪杰斯特拉算法來(lái)說(shuō)影響不大，或者說(shuō)各有各的優(yōu)劣，視問題分析而定。由上面的分析可以看出，迪杰斯特拉算法的難點(diǎn)在于在特殊路徑中找出最短的那條并最后將它刪除。對(duì)于這種情況，其實(shí)我們可以構(gòu)造一個(gè)類來(lái)存儲(chǔ)最短特殊路徑，并使它對(duì)特殊路徑具有push、pop、sort等的功能。不過(guò)STL也提供了類似的類——priority_queue。弗洛伊德沃舍爾（Warshall ）算法沃舍爾算法只需要使用2n^3次位運(yùn)算就可以求出傳遞閉包。傳遞閉包在數(shù)學(xué)中，在集合 X 上的二元關(guān)系R 的傳遞閉包是包含 R 的 X 上的最小的傳遞關(guān)系。當(dāng)圖中點(diǎn)邊關(guān)系以鄰接矩陣給出時(shí)，利用沃舍爾算法能夠在O(n^3)內(nèi)算出每點(diǎn)到各個(gè)點(diǎn)的最短路徑，并以鄰接矩陣形式給出。五行代碼之美如果結(jié)點(diǎn)i與j之間能通過(guò)介質(zhì)點(diǎn)med來(lái)獲得更短路徑，則更新place[i][j]的值共有num_pl個(gè)結(jié)點(diǎn)，place[i][j]表示結(jié)點(diǎn)i到結(jié)點(diǎn)j的邊權(quán)值為place[i][j]，不存在邊時(shí)則賦值INF標(biāo)志。for(int med = 1 。 med = num_pl 。 ++med) for(int i = 1 。 i = num_pl 。 ++i) for(int j = 1 。 j = num_pl 。 ++j) if(place[i][j] place[i][med] + place[med][j]) place[i][j] = place[i][med] + place[med][j] 。
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1