基于改進(jìn)的Kruskal算法求解最短路程問題

1、提供完整版的畢業(yè)設(shè)計研究生綜合應(yīng)用報告課程名稱 高級計算機(jī)網(wǎng)絡(luò) 學(xué) 院 計算機(jī)學(xué)院 年 級 一 專業(yè)班 學(xué) 生 姓 名 張仲勛 學(xué) 號 開 課 時 間 2014 至 2015 學(xué)年 第 一 學(xué)期基于流媒體的高清視頻傳輸摘要本文使用適當(dāng)改進(jìn)的Kruskal算法，解決為使總路程最短如何選擇出行路線的問題。把要到訪的地點作為頂點，所有頂點兩兩之間的連線和距離（起點和終點無連線）分別作為邊以及邊的權(quán)值，構(gòu)造加權(quán)無向圖。問題即轉(zhuǎn)化為尋求從起點出發(fā)，遍歷中間各點，最后到達(dá)終點的最短路徑。該路徑是無向圖的生成樹，但不一定是最小生成樹。路徑的起點和終點已經(jīng)固定，他們的度數(shù)必須為1，而中間各頂點的度數(shù)必須為2，

2、原因在問題分析里面進(jìn)行說明。通過對Kruskal算法適當(dāng)改進(jìn)可以得到該路徑。關(guān)鍵詞：最短路徑 生成樹 Kruskal算法一、 問題分析對于該類問題，要先得到任意兩個地點之間的距離，因為不能直接從起點到達(dá)終點，所以不需要知道起點和終點的直接距離，也即在其加權(quán)圖上這兩點之間沒有邊?？梢酝ㄟ^百度地圖1等工具獲取兩個地點的距離。由于路徑的起點和終點固定，起點只能“出去”，終點只能“進(jìn)來”，當(dāng)求其最短路徑時，這兩個點的度數(shù)要為1。對于起點和終點之外的其他頂點，其度數(shù)只能為2，原因如下：對于任意三個頂點（起點和終點除外）A、B、C，假如A的度數(shù)為3（大于3時只考慮和A相臨的其中兩點），如圖1所示。圖1：一

3、點的度數(shù)大于2設(shè)A先到B點，要經(jīng)過C點的話必須回到A，再到C，其路程必然比從B直接到C遠(yuǎn)。這種情形也包含某個點的度數(shù)為1的情況，所以除起點和終點外其他頂點的必為2。綜上所述，在改進(jìn)Kruskal算法時，只需加上兩個限制條件即可，即起點的度數(shù)為1，其余頂點度數(shù)為2。二、 模型建立把每個地點作為頂點，每兩個頂點相連作為邊，兩個頂點之間的距離作為邊的權(quán)值，構(gòu)造加權(quán)無向圖，如圖2所示（單位：千米）。其中a代表重慶，b代表五臺山，c代表黃鶴樓，d代表泰山，e代表北京，。由于不能從出發(fā)點直接到達(dá)終點，所以a到e沒有連線。圖2：路線模型圖三、 符號說明：存放生成樹的邊的集合，初態(tài)為空集；：生成樹的權(quán)值，初值

4、為零；VS：部分樹的頂點集的集合，初值為：a，b，c，d，e；：頂點的度數(shù)。四、 Kruskal算法改進(jìn)Kruskal算法步驟2：，0，VSa，b，c，d，e，將邊按權(quán)值小到大排成隊列Q；若= 1，輸出，停止。否則轉(zhuǎn)入下一步；從Q中取出邊，并從Q中刪除；如果u，v在VS的同一個元素中，則轉(zhuǎn)，否則分屬兩個集合，進(jìn)入下一步；，VSVS + ，+，轉(zhuǎn)入。由問題分析可知，在對Kruskal算法進(jìn)行改進(jìn)時，只需添加兩個限制條件，起點和終點的度數(shù)為1，其余各點度數(shù)為2。引入來表示頂點的度數(shù)，初值為0，把Kruskal算法的第步改為如下形式：如果u，v在VS的同一個元素中，或者 (，u，v不是起點或終點)，

5、或者 (，u，v是起點或終點)，則轉(zhuǎn)，否則u，v分屬兩個集合，+ 1，+ 1，進(jìn)入下一步。五、問題求解使用改進(jìn)的Kruskal算法求圖2的最小生成樹，按邊的權(quán)值從小到大排列為：，步驟如下：（1） 選出邊，得到= ，= 359，VS = ，；+ 1 = 1；+ 1 = 1；（2） 選出邊，由于的度只能為1，重新選邊；（3） 選出邊，由于b，d分屬VS的兩個不同的集合，= 1，= 0，故得到=，VS =，a，c， = 359 + 576=935，+ 1 = 2，+ 1 = 1；（4） 選出邊，由于c，d分屬VS的兩個不同的集合，= 0，= 1，故得到=，VS = ，a ，= 935+863 = 1798，+ 1 = 1，+ 1 = 2；（5） 選出邊，由于a，c分屬VS的兩個不同的集合，= 0，= 1故得到=，VS = ，= 1798+896 = 2694，+ 1 = 1，+ 1 = 2；（6） 因=1，輸出=，= 2694，計算停止。的圖形如圖2所示，即是通過改進(jìn)的Kruskal算法求得的最小生成樹。圖2：最短路線圖由圖2可知，當(dāng)如下安排行程：重慶到黃鶴樓，黃鶴樓到泰山，