• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 18,  comments - 5,  trackbacks - 0

              在加權圖中,我們經常需要找出兩個指定點之間的最短路,這類問題有如下兩種形式:
               1、單個點到圖中各個點的距離
              
            2、圖中任意兩個點之間的距離

            一、 單個點到圖中各個點的距離



            這類題目主要有兩個算法:
            Bellman-Ford算法,時間復雜性為O(n3),關于其算法的描述及其優化:
            http://www.shnenglu.com/Icyflame/archive/2009/05/02/81662.html
            Dijkstra算法,時間復雜性為O(n2),描述如下:
             1 Dijkstra(G, u)
             2     for each vertex v in V(G)
             3         L[v] = ∞
             4     L[u] = 0
             5     S = {u}
             6     while S != V(G)
             7         v = vertex in V(G)-S with the minimum L-value
             8         S = S + {v}
             9         for each vertex a in V(G)-S
            10             if L[v] + w[v, a] < L[v]
            11                 L[v] = L[v] + w[v, a]
            定理:Dijkstra算法能求出u到G中其它各個點的距離最短
            證明:令k表示6行迭代的次數
            (1) 當k=0時,即初始化后,L[u]為0,S為{u},顯然滿足如下兩個條件:
            • 對于在S中的任意頂點v都有L[v]為u到v的最短路的長度
            • 對于不再S中的任意點v都有L[v]為u只經過S中的點到v的最短路的長度
            (2) 假設k-1次迭代后,滿足上述條件,對于第k次迭代時,選取vk作為加入S點。
                假設L[vk]不是從uvk的最短路的長度,由于vk不在k-1次迭代后的S中,則根據上述條件2可知在uvk的最短路Pu=v1,v2,…,vk,中必存在一個經過一個不在S中的點vi(不為vk),使得v1,…,vi-1S中,則L[vi]uvi的最短路得長度,則有L[vi]<uvk的最短路的長度<L[vk],這與算法第7行中vk的選取條件矛盾。證畢。

            二、 圖中任意兩個點之間的距離



            這類問題有個十分直觀的方法,就是對每個點運行Dijkstra算法,時間復雜性為O(n3),而且也是一個性能較好的方法。
            下面是一個著名的算法—Floyd-Warshall算法,時間復雜性也是O(n3):
             1 Warshall(G)
             2     for i 1 to n
             3         for j 1 to n
             4             if vi in adj[vj]
             5                 d[i, j] = w[i, j]
             6             else
             7                 d[i, j] = ∞
             8     for k 1 to n
             9         for i 1 to n
            10             for j 1 to n
            11                 d[i, j] = min(d[i, j], d[i, k]+d[k, j])
            這個算法其實是一個動態規劃的形式,令d[i, j, k]表示vi與vj經過前k個點的最短距離,則可得遞歸式:
            d[i, j, 0] = w[i, j] 當vi與vj相鄰
            d[i, j, 0] = ∞ 當vi與vj不相鄰
            d[i, j, k+1] = min(d[i, j, k], d[i, k, k]+ d[k, j, k])


            posted on 2009-05-22 22:49 Icyflame 閱讀(516) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
            久久精品国产亚洲AV高清热| 69久久精品无码一区二区| 一级a性色生活片久久无| 久久久精品国产免大香伊| 久久精品国产亚洲AV无码娇色| 精品一区二区久久| 亚洲日本久久久午夜精品| 久久超碰97人人做人人爱| 国内精品久久久久影院网站| 亚洲人成精品久久久久| 久久精品国产72国产精福利| 麻豆亚洲AV永久无码精品久久| 精品久久久久久99人妻| 久久久久99精品成人片直播| 亚洲国产精品综合久久一线| 亚洲一区中文字幕久久| 久久亚洲精品人成综合网| 中文字幕精品久久久久人妻| 国产高潮国产高潮久久久91| 久久精品99久久香蕉国产色戒 | 伊人丁香狠狠色综合久久| 久久久久久精品免费免费自慰| 99久久国产亚洲高清观看2024| 精品国产乱码久久久久软件| 人妻无码久久精品| 久久久精品波多野结衣| 伊人久久综在合线亚洲2019| 久久亚洲精品视频| 久久精品国产亚洲av水果派 | 久久久久人妻精品一区二区三区| 久久无码AV一区二区三区| 久久成人国产精品一区二区| 国产精品99久久不卡| 精品久久久无码中文字幕天天| 精品国产综合区久久久久久| 久久久精品久久久久久| 内射无码专区久久亚洲| 久久无码AV一区二区三区| 无码人妻久久一区二区三区免费丨| 精品国产青草久久久久福利| 久久99久久99精品免视看动漫|