成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【你該懂一點Javascript算法系列】之單源最短路徑 - Dijkstra算法

SoapEye / 1528人閱讀

摘要：算法系列單源最短路徑算法迪杰斯特拉算法是由荷蘭計算機科學(xué)家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。

Javascript算法系列 - 單源最短路徑 - Dijkstra算法 
迪杰斯特拉算法是由荷蘭計算機科學(xué)家狄克斯特拉于1959
年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止

ps: Dijkstra算法是一種貪心算法

以上圖為例 
我們要求出頂點A到其余各頂點間的最短路徑

首先我們先定義出上圖的鄰接矩陣

let graph = [[0,2,4,0,0,0],
             [0,0,1,4,2,0],
             [0,0,0,0,3,0],
             [0,0,0,0,0,2],
             [0,0,0,3,0,2],
             [0,0,0,0,0,0]]

ps: 鄰接矩陣的意思是： 用一個二數(shù)組表示個頂點間的關(guān)系，來確定各頂點間的關(guān)系，因為圖為有向圖，所以上圖的鄰接矩陣如上

先放出Dijkstra算法的全部代碼再來結(jié)合慢慢解析

let index = "ABCDEF"
let INF = Number.MAX_SAFE_INTEGER //1

function dijkstra(src) {
  let dist = [],//2
      visited = [],//3
      length = graph.length//4

  for (let i = 0; i < length; i++) {
    dist[i] = INF
    visited[i] = false 
  }//5
  dist[src] = 0

  for (let i = 0; i < length - 1; i++) {
    let u = minDistance(dist, visited)
    visited[u] = true
    
    for (let v = 0; v < length; v++) {
      if (!visited[v] && dist[u] !== INF && graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
        dist[v] = dist[u] + graph[u][v]
      }
    }
  }

  return dist
}

function minDistance(dist, visited) {
  let min = INF,
      minIndex = -1
  
  for (let v = 0; v < dist.length; v++) {
    if (visited[v] === false && dist[v] <= min) {
      min = dist[v]
      minIndex = v
    }
  }
  
  return minIndex
}

1.初始化數(shù)據(jù)
定義 dist 數(shù)組來儲存當(dāng)前A頂點到其它各個頂點間的距離
定義 visited 數(shù)組來儲存ABCDEF頂點是否被訪問過，以免重復(fù)訪問，形成環(huán)
定義 length 來儲存所有頂點的數(shù)量
定義 INF 為javascript的最大整數(shù) Number.MAX_SAFE_INTEGER

for (let i = 0; i < length; i++) {
    dist[i] = INF
    visited[i] = false 
  }//5
  dist[src] = 0
初始化dist visted 數(shù)組，把所有頂點距離初始化為無限大，所有頂點定義為為訪問
把頂點A到自己的距離初始化為0

2.過程解析

//頂點探索函數(shù)
for (let i = 0; i < length - 1; i++) {
    let u = minDistance(dist, visited)
    visited[u] = true
    
    for (let v = 0; v < length; v++) {
      if (!visited[v] && dist[u] !== INF && graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
        dist[v] = dist[u] + graph[u][v]
      }
    }
  }
//尋找最短路徑函數(shù)
function minDistance(dist, visited) {
  let min = INF,
      minIndex = -1
  
  for (let v = 0; v < dist.length; v++) {
    if (visited[v] === false && dist[v] <= min) {
      min = dist[v]
      minIndex = v
    }
  }
  
  return minIndex
}

具體探索邏輯如下

第一次循環(huán)
找到最短頂點A
遍歷A到其他頂點的距離，如果和其他頂點有直接聯(lián)系，則判斷A到其他頂點的距離，是否是A目前到X頂點的距離 + X到新頂點的距離 < A新頂點的距離
如果小于，則更新到該頂點最短距離

第一次循環(huán)完后相應(yīng)輸出值
發(fā)現(xiàn)A
遍歷發(fā)現(xiàn)A -> B為2 A->C為4 均小于無窮大，所以更新A點到B，C的最短距離

visited -> [ true, false, false, false, false, false ]
dist -> [ 0, 2, 4, 9007199254740991, 9007199254740991, 9007199254740991 ]

第二次循環(huán)
找到最短的那個邊，除A以外 所以探索B點
遍歷發(fā)現(xiàn) B->C,B->E, B->D分別為1，2，4
則
A-C距離為A-B + B-C = 3小于直接到C的距離4 所以更新A-C最短距離

visited -> [ true, true, false, false, false, false ]
dist -> [ 0, 2, 3, 6, 4, 9007199254740991 ]

剩下三次探索輸出為
dist -> [ 0, 2, 3, 6, 4, 9007199254740991 ]
visited -> [ true, true, true, false, true, false ]
dist -> [ 0, 2, 3, 6, 4, 6 ]
visited -> [ true, true, true, false, true, true ]
[ 0, 2, 3, 6, 4, 6 ]

這樣就會獲得A到所有邊的最短距離
[ 0, 2, 3, 6, 4, 6 ]

這就是js實現(xiàn)Dijkstra算法的過程，有些簡短，有問題可以留言交流

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/101454.html

相關(guān)文章

  • 圖算法

    摘要：最小距離相關(guān)算法算法單源最短路徑算法路徑大于零定義概覽迪杰斯特拉算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。注意該算法要求圖中不存在負權(quán)邊。算法可視化代碼 最小距離相關(guān)算法 Dijkstra算法 單源最短路徑算法 路徑大于零 1.定義概覽 Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點...

    chavesgu 評論0 收藏0

  • 面試算法實踐與國外大廠習(xí)題指南

    摘要：面試算法實踐與國外大廠習(xí)題指南翻譯自維護的倉庫，包含了在線練習(xí)算法概述與大廠習(xí)題實戰(zhàn)等內(nèi)容。面試算法實踐與國外大廠習(xí)題指南在線練習(xí)在線面試編程數(shù)據(jù)結(jié)構(gòu)鏈表即是由節(jié)點組成的線性集合，每個節(jié)點可以利用指針指向其他節(jié)點。 面試算法實踐與國外大廠習(xí)題指南 翻譯自 Kevin Naughton Jr. 維護的倉庫 interviews，包含了在線練習(xí)、算法概述與大廠習(xí)題實戰(zhàn)等內(nèi)容。筆者發(fā)現(xiàn)正好和...

    genedna 評論0 收藏0

  • 【你該懂一點Javascript算法系列】之【圖類】的定義及深度優(yōu)先與廣度優(yōu)先搜索算法

    摘要：鄰接矩陣在鄰接矩陣實現(xiàn)中，由行和列都表示頂點，由兩個頂點所決定的矩陣對應(yīng)元素表示這里兩個頂點是否相連如果相連這個值表示的是相連邊的權(quán)重。直到返回到頂點完成探索具體還有版的深度和廣度優(yōu)先的算法，具體代碼奉上直達地址 圖github直達地址 https://github.com/fanshyiis/... 在計算機科學(xué)中，一個圖就是一些頂點的集合，這些頂點通過一系列邊結(jié)對（連接）。頂點用圓...

    qqlcbb 評論0 收藏0

  • 最短路徑算法總結(jié)

    摘要：對于邊權(quán)為正的圖，任意兩個結(jié)點之間的最短路，任意一條的結(jié)點數(shù)不會超過，邊數(shù)不會超過。我會說只有三個嗎適用于任何圖，不管有向無向，邊權(quán)正負，但是最短路必須存在。定義（還記得這些定義嗎？如果對 圖的概念 和 存儲 不了解請點擊鏈接）路徑最短路有向圖中的最短路、無向圖中的最短路單源最短路、每對結(jié)點之間的最短路性質(zhì)對于邊權(quán)為正的圖，任意兩個結(jié)點之間的最短路，不會經(jīng)過重復(fù)的結(jié)點。對于邊權(quán)為正的圖，任意...

    Tecode 評論0 收藏0

  • 【程序員必會十大算法】之弗洛伊德算法

    摘要：學(xué)習(xí)資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設(shè)置為，否則兩個相加會溢出導(dǎo)致出現(xiàn)負權(quán)創(chuàng)建頂點和邊 學(xué)習(xí)資料 迪杰斯特拉計算的是單源最...

    JellyBool 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<