imsz5460
通信網(wǎng)絡規(guī)劃的最短路徑（最小生成樹的2種算法介紹）
《大話數(shù)據(jù)結構》中在“圖”的那一章節(jié)有這樣一個實例：假設你是電信實施工程師，需要為一個鎮(zhèn)的九個村莊架設通信網(wǎng)絡做設計。村莊位置大致如下圖，之間連線的數(shù)字表示村與村間的可通達直線距離（個別如v0與v6，v6與v8，v5與v7未測算距離是因為有高山或湖泊，不予考慮）。你們領導要求你必須用最小的成本完成這次任務。你說怎么辦？
我之前在某家設計院也是做網(wǎng)絡規(guī)劃設計的，而且覺得很有實際意義，所以拿出來給大家分享一下。其實這個案例就是查找連通網(wǎng)的最小生成樹。這術語不懂也沒關系，我們不管它叫什么。
有人說，這還不簡單嘛，我憑著直覺就能做出來。不排除你有這種能力，有時候人類的“直覺”真的是強大，也不知道人類是如何進化到這么聰慧的。
有人說，把所有可能的方案羅列出來，再一一比對，找到最短路徑的那個方案，就行了。這確實是個好辦法，實際上我們也是這樣做的。那么怎么去羅列所有的方案呢？。
為了便于描述上面的圖，我們構造圖的鄰接矩陣。如下圖所示：
在單純的計算或者有規(guī)律的運算方面，我們很容易想到借助計算機來幫忙解決。 剛剛我提到人類的直覺是很強大的，比如有的人答題的時候直接省略了步驟得出了結果，而要他寫詳細的步驟可能他也說不太清。計算機是沒有直覺的，某些我們認為很簡單的東西她可能要運算很多次，而且你還得教她怎樣按照她自己“有限的能力”去執(zhí)行，可是往往我們不知道怎么去教計算機，也就是具體的怎樣寫代碼。
這里介紹兩種思路，也就是兩個算法：
一、一種思路是這樣的：
從v0（可以任意選定一點，這里選v0）開始，找到與其相連的最短的路徑，定義兩個一維數(shù)組a，b。a存儲相關頂點的權值（邊長度），b存儲對應的頂點。路徑(b[i],i)的權值為a[i].i為0至8的整數(shù)，v0為起點至各點的權值如下所示（實際中我們用65535來代表無窮大）。
求a數(shù)組中的最小值，為10，對應的i為1，標記邊（v0，v1）并讓ai置為0，代表vi已經(jīng)納入生成路徑了（此時i為1）。
然后從v1開始，排除a[i]=0對應的頂點vi，當（v1，vi）的權值小于此時a[i]的值，將前者替換掉后者，更新a數(shù)組的值。
求a數(shù)組中的最小值，為11，對應的i為5，標記邊（v0，v5）并讓a5置為0，代表v5已經(jīng)納入生成路徑了。
然后從v5開始，排除a[i]=0對應的頂點vi，當（v5，vi）的權值小于此時a[i]的值，將前者替換掉后者，更新a數(shù)組的值。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動安全 [無線安全]玩轉(zhuǎn)無線電——不安全的藍牙鎖 2017-07-26
- 消息隊列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標分割】 2017-07-26
- 詞向量-LRWE模型-更好地識別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動安全 Android端惡意鎖屏勒索應用分析 2017-07-26
- 集合結合數(shù)據(jù)結構來看看(二) 2017-07-26
學習是年輕人改變自己的最好方式