欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2021年09月06日 09:14:58   作者:豆沙包lo  
這篇文章主要介紹了Dijkstra算法與Prim算法的異同案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下

Dijkstra簡述

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

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

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

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

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

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

思想

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

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

時間復雜度

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

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

Dijkstra特例

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

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

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

總的時間復雜度

TIME = V + E

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

相關文章

  • C++ string 字符串查找匹配實例代碼

    C++ string 字符串查找匹配實例代碼

    下面小編就為大家?guī)硪黄狢++ string 字符串查找匹配實例代碼。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-10-10
  • C++實現(xiàn)Dijkstra算法的示例代碼

    C++實現(xiàn)Dijkstra算法的示例代碼

    迪杰斯特拉算法(Dijkstra)是由荷蘭計算機科學家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法。本文將用C++實現(xiàn)Dijkstra算法,需要的可以參考一下
    2022-07-07
  • C語言代碼實現(xiàn)猜數(shù)字

    C語言代碼實現(xiàn)猜數(shù)字

    這篇文章主要為大家詳細介紹了C語言代碼實現(xiàn)猜數(shù)字,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-11-11
  • 解析C語言結構體及位段

    解析C語言結構體及位段

    今天小編就為大家分享一篇關于解析C語言結構體及位段,小編覺得內容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2018-12-12
  • C語言測試n的階乘和x的n次方

    C語言測試n的階乘和x的n次方

    今天小編就為大家分享一篇關于C語言測試n的階乘和x的n次方,小編覺得內容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2019-02-02
  • C++深入分析STL中map容器的使用

    C++深入分析STL中map容器的使用

    map在編程中是經常使用的一個容器,本文來講解一下STL中的map,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-05-05
  • 簡單分析針對ARM平臺的C語言程序的編譯問題

    簡單分析針對ARM平臺的C語言程序的編譯問題

    這篇文章主要介紹了針對ARM平臺的C語言程序的編譯問題,從優(yōu)化編譯選項的幾個方面進行分析,需要的朋友可以參考下
    2015-12-12
  • c++實現(xiàn)簡單的線程池

    c++實現(xiàn)簡單的線程池

    本文介紹的線程池采用C++語言,在windows平臺下實現(xiàn)。本著技術分享的精神寫作本文同時公布源代碼。歡迎大家指出該線程池存在的問題并對當前性能進行討論。
    2015-03-03
  • linux下使用g++編譯cpp工程的方法

    linux下使用g++編譯cpp工程的方法

    這篇文章主要介紹了linux下使用g++編譯cpp工程的相關知識,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-03-03
  • 常用的STL查找算法

    常用的STL查找算法

    這篇文章主要介紹了常用的STL查找算法的相關資料,十分的詳細,需要的朋友可以參考下
    2015-07-07

最新評論