imsz5460
通信網(wǎng)絡(luò)規(guī)劃的最短路徑（最小生成樹的2種算法介紹）
《大話數(shù)據(jù)結(jié)構(gòu)》中在“圖”的那一章節(jié)有這樣一個實例：假設(shè)你是電信實施工程師，需要為一個鎮(zhèn)的九個村莊架設(shè)通信網(wǎng)絡(luò)做設(shè)計。村莊位置大致如下圖，之間連線的數(shù)字表示村與村間的可通達(dá)直線距離（個別如v0與v6，v6與v8，v5與v7未測算距離是因為有高山或湖泊，不予考慮）。你們領(lǐng)導(dǎo)要求你必須用最小的成本完成這次任務(wù)。你說怎么辦？
我之前在某家設(shè)計院也是做網(wǎng)絡(luò)規(guī)劃設(shè)計的，而且覺得很有實際意義，所以拿出來給大家分享一下。其實這個案例就是查找連通網(wǎng)的最小生成樹。這術(shù)語不懂也沒關(guān)系，我們不管它叫什么。
有人說，這還不簡單嘛，我憑著直覺就能做出來。不排除你有這種能力，有時候人類的“直覺”真的是強(qiáng)大，也不知道人類是如何進(jìn)化到這么聰慧的。
有人說，把所有可能的方案羅列出來，再一一比對，找到最短路徑的那個方案，就行了。這確實是個好辦法，實際上我們也是這樣做的。那么怎么去羅列所有的方案呢？。
為了便于描述上面的圖，我們構(gòu)造圖的鄰接矩陣。如下圖所示：
在單純的計算或者有規(guī)律的運(yùn)算方面，我們很容易想到借助計算機(jī)來幫忙解決。 剛剛我提到人類的直覺是很強(qiáng)大的，比如有的人答題的時候直接省略了步驟得出了結(jié)果，而要他寫詳細(xì)的步驟可能他也說不太清。計算機(jī)是沒有直覺的，某些我們認(rèn)為很簡單的東西她可能要運(yùn)算很多次，而且你還得教她怎樣按照她自己“有限的能力”去執(zhí)行，可是往往我們不知道怎么去教計算機(jī)，也就是具體的怎樣寫代碼。
這里介紹兩種思路，也就是兩個算法：
一、一種思路是這樣的：
從v0（可以任意選定一點(diǎn)，這里選v0）開始，找到與其相連的最短的路徑，定義兩個一維數(shù)組a，b。a存儲相關(guān)頂點(diǎn)的權(quán)值（邊長度），b存儲對應(yīng)的頂點(diǎn)。路徑(b[i],i)的權(quán)值為a[i].i為0至8的整數(shù)，v0為起點(diǎn)至各點(diǎn)的權(quán)值如下所示（實際中我們用65535來代表無窮大）。
求a數(shù)組中的最小值，為10，對應(yīng)的i為1，標(biāo)記邊（v0，v1）并讓ai置為0，代表vi已經(jīng)納入生成路徑了（此時i為1）。
然后從v1開始，排除a[i]=0對應(yīng)的頂點(diǎn)vi，當(dāng)（v1，vi）的權(quán)值小于此時a[i]的值，將前者替換掉后者，更新a數(shù)組的值。
求a數(shù)組中的最小值，為11，對應(yīng)的i為5，標(biāo)記邊（v0，v5）并讓a5置為0，代表v5已經(jīng)納入生成路徑了。
然后從v5開始，排除a[i]=0對應(yīng)的頂點(diǎn)vi，當(dāng)（v5，vi）的權(quán)值小于此時a[i]的值，將前者替換掉后者，更新a數(shù)組的值。
