【文章內容簡介】 止: G1={v1}G2={v1，v3}G3={v1，v3，v6}G4={v1，v3，v6，v7}G5={v1，v3，v6，v7，v2}G6={v1，v3，v6，v7，v2，v5}G7={v1，v3，v6，v7，v2，v5，v4}則W(T)=15 可以看出， Prim算法第K步運算，是以Gk作為整體尋找至GGk的最短邊，每次并入Gk的邊總是保持余下mk+1個中最短的，因此算法終止時，所得的支撐樹為最短者(可用數(shù)學歸納法證明)。 從算法始至終止，共進行n1步，每步從k個端與nk個端比較，須經k(nk)1次，可得總計算量 約為n3量級。當n很大時，可借助計算機實現(xiàn)。另一個算法由Kruskal在1956年提出:設G(k)是G的無圈支撐子圖,開始G(0)=(V,f)。若G(k)是連通的,則它是最小支撐樹；若G(k)不連通,取e(k)為這樣的一邊,它的兩個端點分屬G(k)的兩個不同連通分圖,并且權最小。令G(k+1)= G(k)+ e(k),重復上述過程。上面算法的實現(xiàn)過程需要排序算法；Rosenstiehl和管梅谷提出了另一個算法：設G(k)是G的連通支撐子圖，開始G(0)=G，若G(k)中不含圈，則它是最小支撐樹；若G(k)中包含圈，設m是G(k)中的一個圈，取m上的一條權最大的邊e(k)，令G(k+1)= G(k)e(k)，重復上述過程。上面算法的實現(xiàn)過程需要解決如小問題：對于一個無向圖G, 如何尋找其中的圈?可以通過搜索圖中度為1的頂點而逐步簡化.上面算法的實施過程,都是一種貪心法原理的應用。 , 這種方法一般只能找到準最優(yōu)解.2) 有限制情況 在許多情況下，不但要求最短支撐樹，還要求一些額外條件。有兩種解決此類問題的方法窮舉法和調整法。窮舉法就是先把圖中的支撐樹窮舉出來，按條件逐個篩選，最后選出最短支撐樹。這種方法較直觀，但很煩瑣。下面討論調整法。以EsauWilliam算法為例(解決一種特定的問題):問題:圖G有n個站,其中已知v1是主機，已知各邊間距離dij，以及各個端站的業(yè)務量Fi（i，j=1，2，…，n），要求任端至v1的徑邊數(shù)K(即限轉接次數(shù)K1)，且徑上總業(yè)務量163。M，(其中K為給定的整數(shù),M為給定的實數(shù)),求最短支撐樹 算法主要思想: 從上圖開始(星形樹),采用貪心法原則,逐步用邊替換vi至v1的邊,為此需要計算轉接損失矩陣, 每次選用一條邊使新樹的長度減少最多,但每次要注意新樹是否滿足限制條件。實質上，每次都和上次得到的樹做比較，看看能否有進展。步驟：EW0：起始，n個端為n個部分，鄰接陣為全零陣；EW1：計算到v1各個部分的距離D1i，和不在同一個部分內的兩端之間的邊的轉接損失tij EW2： 測試增加邊(i*,j*)邊后是否仍滿足條件，若滿足，在鄰接陣置 ；若不滿足，則重復EW2； EW3：考慮形成的新的部分，若部分數(shù)大于1，返回；等于1，終止； 說明：若(其中K=3, M=50)： 計算T矩陣：t34=11 最小，取邊（3, 4）最替換邊(3, 1)；如此反復，最后得樹為: {(3, 4), (4, 1), (2, 5), (5, 1)}樹長=12上面的例中, 如果將邊(3, 2), (2,1)和(4, 5)的權改為2, , 容易得到一個簡單的反例, 存在一個樹長為11的支撐樹, 也滿足問題中要求的限制條件，說明上述EW算法得到的不是全局最優(yōu)解.167。、端間最短徑 當網絡結構已定，我們需要尋找端間的最短距離和路由。分兩種情況： 尋找指定端至其它端的最短徑和路由，我們采用Dijkstra算法； 尋找任意二端最短徑和路由, 用Floyd算法。1)指定端至其它端最短徑和路由算法: 已知 圖G=(V，E)及dij ，求端vs至其它端的最短徑和路由，用Dijkstra算法： 由上圖可以看出： 直邊不一定是最短徑，如ds2，其實vs與v2間最短徑長為3(經v3轉接)。但可肯定，與vs相連的直邊最小的一個必定為最短徑(如es3)，其它轉接至vs必不短。因此，算法從始找鄰近端， 從vs最鄰近端找起， 每次得一個最短徑。下面我們介紹Dijkstra算法，暫時不考慮端有權, 對于端有權的情況稍后處理。 首先我們會用到下列計算中的名詞： 置定：某端置定即表示得到了至該端的最短徑 標值：至該步時的暫時最短徑，（置定端可供轉接） wi為vs 174。vi暫時的的最短徑長 wj*為vs 174。vi的置定時的最短徑長Dijkstra算法步驟：端點集合Vp表示置定的端點集合, V Vp為沒有置定的端點集合。D0 開始置定vs，ws*=0（vs 174。vs），其它端暫置wj=165。( 如果邊(s, j)存在, wj = ds,j)D1 計算未置定端vj的標值的公式 wj :=min（wj，wi +dij）, 其中vi206。Vp vj206。V VpD2 取最小值, wj* = min wj 然后, 置定端vj*206。Vp 。 當所有端置定，算法結束. 不然, 返回D1.上面的算法沒有給出取得最短徑的路由, 不過對于路由可以很簡單處理. 路由的給出方法可以有許多種, 如前向路由和回溯路由等. 對于Dijkstra算法, 可以給出回溯路由, 即給出最短徑的前一個端點的標號, 而這個端點標號可以在算法D1的更新計算中獲得。 每個端點的標號可以由兩部分組成, 即距離和前一個端點標號. ： Vs V1 V2 V3 V4置定端 距離 路由0 165。 165。 165。 165。 8 4 2 6 8 3 5 6 5 6Vs 0 sV3 2 s V2 3 3V4 5 3V1 6 2 D算法計算量:當有個k端已置定，需做(nk)次加法，(nk)次比較以更新各端的暫定值，(nk1)次比較求最小值，則總計算量約為對于Dijkstra算法, 提出若干問題如下: 1 如果端點有權如何處理? 2 如果邊的權可正可負, 算法是否仍然有效? 3 算法是否對有向圖也適用？上面Dijkstra算法中使用的為Labelsetting的方法, 下面介紹一個用Labelcorrecting技術的方法, 效率要高許多。不失一般性，假設是G一個有向圖，用d(i)記從s至i的距離，pred(i)記路由s→i的上一個頂點(回朔路由), A(i)記錄從i出發(fā)的所有邊的集合。算法如下：begin d(s):=0 and pred(s):=0。 d(j):=∞ for each j∈V{s}。 List:={s}。 while List 185。 f do begin 從 List中去掉一個元素i 。 對每個邊(i, j) ∈A(i) doif d(j)