Dijkstra算法與Prim算法的異同案例詳解

Dijkstra簡述

Dijkstra算法用於構建單源點的最短路徑樹(MST)——即樹中某個點到任何其他點的距離都是最短的。例如,構建地圖應用時查找自己的坐標離某個地標的最短距離。可以用於有向圖,但是不能存在負權值(Bellman-Ford可以處理負權值)。

  • 偽代碼
Dijkstra() {
    for each u in G,V {
        //此處做初始化操作,給每個節點u賦鍵值+∞,設置空為父節點
        u.key = +∞
        u.parent = NULL
    }
    //選初始點r,Q是無向圖G中所有點V的權值優先隊列,key可看作源點到u的距離
    r.key = 0
    Q = G,V
    while(Q != ∅) {
          //取出Q中權值最小值的點u
          u = extractMin(Q) 
          //取點u連接的所有節點(即無向圖G的鄰接表中的第u個鏈表)
          for each v ∈ G.Adj[u] {
              if (v ∈ Q) and (w(u, v) < key) {
                  //若該節點仍在Q中且權值w(w,v)小於其原始權值,則進行松弛操作!
                  v.parent = u
                  v.key = w(u, v) + u.key
              }
          }
      }
}

Prim簡述

Prim算法用於構建最小生成樹——即樹中所有邊的權值之和最小。例如,構建電路板,使所有邊的和花費最少。隻能用於無向圖

  • 偽代碼
//無向圖G, 權值w, 起始點r
MST(G, w, r) {
    for each u in G,V {
        //此處做初始化操作,給每個節點u賦鍵值+∞,設置空為父節點
        u.key = +∞
        u.parent = NULL
    }
    //選初始點r,Q是無向圖G中所有點V的權值優先隊列,key可看作u到下一個節點v的距離
    r.key = 0
    Q = G,V
    while(Q != ∅) {
          //取出Q中權值最小值的點u
          u = extractMin(Q) 
          //取點u連接的所有節點(即無向圖G的鄰接表中的第u個鏈表)
          for each v ∈ G.Adj[u] {
              if (v ∈ Q) and (w(u, v) < key) {
                  //若該節點仍在Q中且權值w(w,v)小於其原始權值,則進行松弛操作!
                  v.parent = u
                  v.key = w(u, v)
              }
          }
      }
}

MST中任意AB兩點之間的距離,並不比原始圖中AB的距離短,即原始圖中可能存在邊E(A,B)**小於**MST中的E(A,B)。

註意上述兩個偽算法的差別隻在於最後循環體內的松弛操作

  • 最小生成樹隻關心所有邊的和最小,所以有v.key = w(u, v),即每個點直連其他點的最小值(最多隻有兩個節點之間的權值和)
  • 最短路徑樹隻搜索權值最小,所以有v.key = w(u, v) + u.key,即每個點到其他點的最小值(最少是兩個節之間的權值和)

簡單總結就是,Dijkstra的松弛操作加上瞭到起點的距離,而Prim隻有相鄰節點的權值。

思想

都是使用貪婪和線性規劃,每一步都是選擇權值/花費最小的邊。
貪婪:一個局部最有解也是全局最優解;
線性規劃:主問題包含n個子問題,而且其中有重疊的子問題。

Dijkstra算法通過線性規劃緩存瞭最優子路徑的解,每一步也通過貪婪算法來選擇最小的邊。
Prim算法通過貪婪來選擇最小的邊,而Prim的每個子樹都是最小生成樹說明滿足線性規劃的兩個條件。

時間復雜度

Time = θ( V * T1 + E * T2)
其中T1為取出鍵值最小點的時間,T2為降低鍵值的時間,取決於數據結構。

  • 數組
    T1= O(V), T2 = O(1), TIME = O(V * V + E) = O(V * V)
  • 二叉堆
    T1 = O(lgV), T2 = O(lgV), TIME = O(V * lgV + E * lgV) 
  • 斐波那契堆
    T1 = O(lgV), T2 = O(1), TIME = O(V * lgV + E) = O(V * lgV)

對於稀疏圖來說,E遠小於V*V,所以二叉堆比較好;
而對於密集圖來說,E=V*V,所以數組比較好;
斐波那契堆是最好的情況。

Dijkstra特例

當邊的權值都為1的時候,可以用DFS(廣度優先搜索)優化時間復雜度。

  • 使用FIFO(先進先出)隊列代替優先隊列,優化瞭降低鍵值T2的操作為O(1)
  • 松弛操作改為
    if d[v] = +∞ {
        d[v] = d[u] + 1
        enqueue(Q, v)
    }

優化瞭取出鍵值最小點的時間T1 = O(1)

總的時間復雜度

TIME = V + E

到此這篇關於Dijkstra算法與Prim算法的異同案例詳解的文章就介紹到這瞭,更多相關Dijkstra算法與Prim算法的異同內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: