最小生成樹(shù)and最短路徑(存儲(chǔ)版)
【正文】 必抽象出對(duì)象出來(lái)。 ++kn ){lowcost[kn] = data[0][kn]。}}每執(zhí)行一次（3）都需要對(duì)著兩個(gè)數(shù)組進(jìn)行更新for (int ks = 0 。21 181 54410 7 30 從1到4最短路徑 1053 9 953 1 1迪杰斯特拉（Dijkstra）算法Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。迪杰斯特拉算法每次從所有特殊路徑中取出最短特殊路徑及其頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。對(duì)于這種情況，其實(shí)我們可以構(gòu)造一個(gè)類(lèi)來(lái)存儲(chǔ)最短特殊路徑，并使它對(duì)特殊路徑具有push、pop、sort等的功能。 med = num_pl 。五行代碼之美如果結(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)志。難點(diǎn)無(wú)論是邊集數(shù)組還是鄰接矩陣來(lái)存儲(chǔ)圖，對(duì)迪杰斯特拉算法來(lái)說(shuō)影響不大，或者說(shuō)各有各的優(yōu)劣，視問(wèn)題分析而定。初始時(shí)，S中僅含有源。 }}時(shí)間復(fù)雜度若n表示圖的結(jié)點(diǎn)數(shù)，那么初始化需要O(n)，找出最小邊O(n)，更新為O(n)，需要找出與更新n次，總的為O(n*(2n)+n)，即O(n*n)。 lowcost[i] min ) {min = lowcost[i] 。所以當(dāng)（2）中采用了第一結(jié)點(diǎn)，那么這個(gè)數(shù)組應(yīng)當(dāng)被初始化為for(int kn = 1。當(dāng)a,b之間沒(méi)有邊的時(shí)候，應(yīng)當(dāng)使data[a][b] = INF（INF表示無(wú)窮）。從指定頂點(diǎn)開(kāi)始將它加入集合中，然后將集合內(nèi)的頂點(diǎn)與集合外的頂點(diǎn)所構(gòu)成的所有邊中選取權(quán)值最小的一條邊作為生成樹(shù)的邊，并將集合外的那個(gè)頂點(diǎn)加入到集合中，表示該頂點(diǎn)已連通。struct edge{ int nod
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1