最小生成樹and最短路徑-閱讀頁
2025-07-08 18:52本頁面
【正文】 lowcost數(shù)組：lowcost[i]表示A集合中到結(jié)點(diǎn)i(I必然在集合B中)的權(quán)值；closest數(shù)組：對應(yīng)與lowcost，表示結(jié)點(diǎn)i到集合A的用最小權(quán)值邊連通的點(diǎn)。 kn n 。closest[kn] = 0 。 i n 。amp。min_site = i 。 ks n 。amp。closest[ks] = min_site 。最短路徑最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題， 旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。但是，由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對應(yīng)的最短特殊路徑長度。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長度。初始化：結(jié)點(diǎn)1作為源點(diǎn)，此時(shí)的特殊路徑有{1114}，最短特殊路徑為131 103明顯結(jié)點(diǎn)3到源點(diǎn)的最短路徑已定，則結(jié)點(diǎn)3也在S集合中，dist[3]被賦值為10。以此類推，直到所有的點(diǎn)的dist被計(jì)算出來。由上面的分析可以看出，迪杰斯特拉算法的難點(diǎn)在于在特殊路徑中找出最短的那條并最后將它刪除。不過STL也提供了類似的類——priority_queue。傳遞閉包在數(shù)學(xué)中，在集合 X 上的二元關(guān)系當(dāng)圖中點(diǎn)邊關(guān)系以鄰接矩陣給出時(shí)，利用沃舍爾算法能夠在O(n^3)內(nèi)算出每點(diǎn)到各個(gè)點(diǎn)的最短路徑，并以鄰接矩陣形式給出。for(int med = 1 。 ++med) for(int i = 1 。 ++i) for(int j = 1 。 ++j) if(place[i][j] place[i][med] + place[med][j]) place[i][j] = place[i][med] + place[med]
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1