<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    E81086713E446D36F62B2AA2A3502B5EB155

    Java雜家

    雜七雜八。。。一家之言

    BlogJava 首頁 新隨筆 聯系 聚合 管理
      40 Posts :: 1 Stories :: 174 Comments :: 0 Trackbacks

    算法:

    設G是帶權圖,圖中的頂點多于一個,且所有的權都為正數。本算法確定從頂點S到G中其他各個頂點的距離和最短通路。在本算法中P表示帶永久標記的頂點的集合。頂點A的前驅是P中的一個頂點,用來標記A。頂點U和V之間的邊的權重用W(U,V)表示,如果U和V之間沒有邊,則記作W(U,V)=∞.

    步驟1 (對S做標記)

          (a)將S標記為0,并使S沒有前驅

          (b)令P={S}

    步驟2 (對其他頂點作標記)

          將每個不在P中的頂點V標記為W(S,V)(可能是暫時的),并使V的前驅為S(可能是暫時的)

    步驟3 (擴大P,修改標記)

         Repeat

         步驟3.1 (是另一個標記永久化)

                      把不在P中且帶有最小標記的頂點U加入到P中去(如果這樣的頂點有多個則任選其中一個)

        步驟3.2  (修改臨時標記)

                    對每個不在P中并且和U相鄰的頂點X,把X的標記替換為下列這兩者中的較小者:i)X的舊標記,ii)U上的標記與W(U,X)之和。如果X的標記改變了,則使U成為X的新前驅(可能是暫時的)

        Until P包含G中的每一個頂點

    步驟4 (求出距離和最短通路)

       頂點Y上的標記是從S到Y的距離。如果Y上的標記是∞,那么從S到Y就沒有通路,從而

    沒有最短通路;否則,按照下列序列的逆序使用頂點就構成從S到Y的一條最短通路:

    Y,Y的前驅,Y的前驅的前驅,。。。。,直至S

     

     

    證明:Dijkstra算法給出了從S到G的各個頂點的最短通路長度。

     

    我們假設G中的每個頂點V都被賦予了一個標記L(V),它要么是一個數,要么是∞。假設P是G的頂點的集合,P包含S,滿足:

    1)如果V屬于P,則L(V)是從S到V的最短通路的長度,并且存在這樣的從S到V的最短通路:通路上的頂點都在P中

    2)如果V不屬于P,則L(V)是從S到V的滿足下面限制的最短通路的長度:V是通路中唯一一個不屬于P的頂點。

     

    我們可以用歸納法證明Dijkstra算法中的P符合上述定義的集合:

    1)當P中元素個數為1時,P對應算法中的第一步,P={S},顯然滿足。

    2)假設P中元素個數為K時,P滿足上述定義,下面看算法的的第三步,

       先找出不在P中且帶有最小標記的頂點U,標記為L(U), 可以證明從S到U的最短通路中除U外不包含不屬于P的元素。

    因為若存在除U外其他頂點,則最短通路為SP1P2...PnQ1Q2...QnU(P1,P2..Pn屬于P,Q1,Q2,...Qn不屬于P),則由性質2)最短通路長度為L(Q1)+PATH(Q1,U)>L(U)

    從而大于SP1P2..PnU的通路長度L(U),不是最短通路,所以從S到U的最短通路中除U外不包含不屬于P的元素,從而從S到U的最短通路長度由L(U)給出.

    現把U加入P中構成P' ,顯然P'滿足性質1)。

    取V不屬于P',顯然V也不屬于P,那么從S到V的最短通路且滿足除V外所有頂點都在P'中的通路有兩種可能,i)包含U,ii)不包含U。

    對i)SP1P2...PnUV=L(U)+W(U,V)

       ii)SP1P2..PnV=L(V)

    顯然二者中的最小給出了從S到V的最短通路且滿足除V外所有頂點都在P'中的長度。

    從而算法第三步給出的P'含K+1個元素且滿足1),2)。

    又歸納,命題得證!

     

    下面是一個Java版的實現:最短路徑的Java實現

    posted on 2007-09-07 13:24 DoubleH 閱讀(6233) 評論(3)  編輯  收藏

    Feedback

    # re: Dijkstra算法及其證明 2007-12-19 22:15 柏拉圓
    “頂點U和V之間的邊上的權”這句話不妥當。
    連接頂點U與V的邊的權重。  回復  更多評論
      

    # re: Dijkstra算法及其證明 2007-12-19 23:19 Javacap
    @柏拉圓
    謝謝提醒,已改過!  回復  更多評論
      

    # re: Dijkstra算法及其證明 2009-04-20 11:16 westwind
    因為若存在除U外其他頂點,則最短通路為SP1P2...PnQ1Q2...QnU(P1,P2..Pn屬于P,Q1,Q2,...Qn不屬于P),則由性質2)最短通路長度為L(Q1)+PATH(Q1,U)>L(U)

    從而大于SP1P2..PnU的通路長度L(U),不是最短通路,所以從S到U的最短通路中除U外不包含不屬于P的元素,從而從S到U的最短通路長度由L(U)給出.

    以上文字表述似可修正為:
    因為若存在除U外其他頂點,設最短通路為SP1P2...PnQ1Q2...QmU(P1,P2..Pn屬于P,Q1,Q2,...Qm不屬于P,m>0)。由性質2),其長度必不小于L(Q1)+PATH(Q1,U),而后者必大于L(U),因而不是由S到U的最短通路,與前設矛盾。所以從S到U的最短通路中除U外不包含不屬于P的元素,從而從S到U的最短通路長度由L(U)給出.

      回復  更多評論
      


    只有注冊用戶登錄后才能發表評論。


    網站導航:
     
    主站蜘蛛池模板: 国产亚洲精品影视在线| 亚洲精品在线观看视频| 亚洲日韩乱码中文字幕| 国产曰批免费视频播放免费s| 亚洲va无码专区国产乱码| 拍拍拍无挡免费视频网站| 亚洲色成人网站WWW永久| a级日本高清免费看| 久久伊人久久亚洲综合| 99精品一区二区免费视频| 亚洲精品韩国美女在线| 噼里啪啦免费观看高清动漫4| 亚洲私人无码综合久久网| 午夜视频免费成人| 国产亚洲精品成人久久网站| 亚洲第一福利网站在线观看| jizz在线免费观看| 久久亚洲中文字幕精品有坂深雪| 久久www免费人成看片| 亚洲国产精品无码久久九九大片| 国产免费看插插插视频| 精品国产呦系列在线观看免费| 中文字幕亚洲综合久久菠萝蜜| 好久久免费视频高清| 亚洲人成网站日本片| 国产精品国产自线拍免费软件| 一级做α爱过程免费视频| 久久精品国产亚洲香蕉| 国产电影午夜成年免费视频| 亚洲精品欧美综合四区| 国产AV无码专区亚洲AV漫画| 久久成人国产精品免费软件| 国产亚洲一卡2卡3卡4卡新区| 亚洲情a成黄在线观看| 2019中文字幕在线电影免费| 亚洲中文字幕无码中文字| 亚洲性久久久影院| 性xxxxx免费视频播放| 九九九国产精品成人免费视频| 久久亚洲AV成人无码国产| 国产在线19禁免费观看|