Dijkstra簡述

Dijkstra算法用于構(gòu)建單源點(diǎn)的最短路徑樹(MST)——即樹中某個(gè)點(diǎn)到任何其他點(diǎn)的距離都是最短的。例如，構(gòu)建地圖應(yīng)用時(shí)查找自己的坐標(biāo)離某個(gè)地標(biāo)的最短距離。可以用于有向圖，但是不能存在負(fù)權(quán)值(Bellman-Ford可以處理負(fù)權(quán)值)。

• 偽代碼

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

Prim簡述

Prim算法用于構(gòu)建最小生成樹——即樹中所有邊的權(quán)值之和最小。例如，構(gòu)建電路板，使所有邊的和花費(fèi)最少。只能用于無向圖。

• 偽代碼

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

異

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

注意上述兩個(gè)偽算法的差別只在于最后循環(huán)體內(nèi)的松弛操作。

• 最小生成樹只關(guān)心所有邊的和最小，所以有v.key = w(u, v)，即每個(gè)點(diǎn)直連其他點(diǎn)的最小值（最多只有兩個(gè)節(jié)點(diǎn)之間的權(quán)值和）
• 最短路徑樹只搜索權(quán)值最小，所以有v.key = w(u, v) + u.key，即每個(gè)點(diǎn)到其他點(diǎn)的最小值（最少是兩個(gè)節(jié)之間的權(quán)值和）

簡單總結(jié)就是，Dijkstra的松弛操作加上了到起點(diǎn)的距離，而Prim只有相鄰節(jié)點(diǎn)的權(quán)值。

同

思想

都是使用貪婪和線性規(guī)劃，每一步都是選擇權(quán)值/花費(fèi)最小的邊。
貪婪：一個(gè)局部最有解也是全局最優(yōu)解；
線性規(guī)劃：主問題包含n個(gè)子問題，而且其中有重疊的子問題。

Dijkstra算法通過線性規(guī)劃緩存了最優(yōu)子路徑的解，每一步也通過貪婪算法來選擇最小的邊。
Prim算法通過貪婪來選擇最小的邊，而Prim的每個(gè)子樹都是最小生成樹說明滿足線性規(guī)劃的兩個(gè)條件。

時(shí)間復(fù)雜度

Time = θ( V * T1 + E * T2)
其中T1為取出鍵值最小點(diǎn)的時(shí)間，T2為降低鍵值的時(shí)間，取決于數(shù)據(jù)結(jié)構(gòu)。

• 數(shù)組
  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遠(yuǎn)小于V*V，所以二叉堆比較好；
而對于密集圖來說，E=V*V，所以數(shù)組比較好；
斐波那契堆是最好的情況。

Dijkstra特例

當(dāng)邊的權(quán)值都為1的時(shí)候，可以用DFS（廣度優(yōu)先搜索）優(yōu)化時(shí)間復(fù)雜度。

• 使用FIFO（先進(jìn)先出）隊(duì)列代替優(yōu)先隊(duì)列，優(yōu)化了降低鍵值T2的操作為O(1)
• 松弛操作改為

    if d[v] = +∞ {
        d[v] = d[u] + 1
        enqueue(Q, v)
    }

優(yōu)化了取出鍵值最小點(diǎn)的時(shí)間T1 = O(1)

總的時(shí)間復(fù)雜度

TIME = V + E

到此這篇關(guān)于Dijkstra算法與Prim算法的異同案例詳解的文章就介紹到這了,更多相關(guān)Dijkstra算法與Prim算法的異同內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論