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

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

 更新時(shí)間:2021年09月06日 09:14:58   作者:豆沙包lo  
這篇文章主要介紹了Dijkstra算法與Prim算法的異同案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

Dijkstra簡(jiǎn)述

Dijkstra算法用于構(gòu)建單源點(diǎn)的最短路徑樹(shù)(MST)——即樹(shù)中某個(gè)點(diǎn)到任何其他點(diǎn)的距離都是最短的。例如,構(gòu)建地圖應(yīng)用時(shí)查找自己的坐標(biāo)離某個(gè)地標(biāo)的最短距離??梢杂糜谟邢驁D,但是不能存在負(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是無(wú)向圖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)(即無(wú)向圖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簡(jiǎn)述

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

  • 偽代碼
//無(wú)向圖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是無(wú)向圖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)(即無(wú)向圖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)的松弛操作。

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

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

思想

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

Dijkstra算法通過(guò)線性規(guī)劃緩存了最優(yōu)子路徑的解,每一步也通過(guò)貪婪算法來(lái)選擇最小的邊。
Prim算法通過(guò)貪婪來(lái)選擇最小的邊,而Prim的每個(gè)子樹(shù)都是最小生成樹(shù)說(shuō)明滿足線性規(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)

對(duì)于稀疏圖來(lái)說(shuō),E遠(yuǎn)小于V*V,所以二叉堆比較好;
而對(duì)于密集圖來(lái)說(shuō),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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++ string 字符串查找匹配實(shí)例代碼

    C++ string 字符串查找匹配實(shí)例代碼

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

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

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

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

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

    解析C語(yǔ)言結(jié)構(gòu)體及位段

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

    C語(yǔ)言測(cè)試n的階乘和x的n次方

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

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

    map在編程中是經(jīng)常使用的一個(gè)容器,本文來(lái)講解一下STL中的map,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-05-05
  • 簡(jiǎn)單分析針對(duì)ARM平臺(tái)的C語(yǔ)言程序的編譯問(wèn)題

    簡(jiǎn)單分析針對(duì)ARM平臺(tái)的C語(yǔ)言程序的編譯問(wèn)題

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

    c++實(shí)現(xiàn)簡(jiǎn)單的線程池

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

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

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

    常用的STL查找算法

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

最新評(píng)論