亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

SoapEye / 1583人閱讀

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

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

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

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

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

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: 鄰接矩陣的意思是： 用一個(gè)二數(shù)組表示個(gè)頂點(diǎn)間的關(guān)系，來(lái)確定各頂點(diǎn)間的關(guān)系，因?yàn)閳D為有向圖，所以上圖的鄰接矩陣如上

先放出Dijkstra算法的全部代碼再來(lái)結(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ù)組來(lái)儲(chǔ)存當(dāng)前A頂點(diǎn)到其它各個(gè)頂點(diǎn)間的距離
定義 visited 數(shù)組來(lái)儲(chǔ)存ABCDEF頂點(diǎn)是否被訪問(wèn)過(guò)，以免重復(fù)訪問(wèn)，形成環(huán)
定義 length 來(lái)儲(chǔ)存所有頂點(diǎn)的數(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ù)組，把所有頂點(diǎn)距離初始化為無(wú)限大，所有頂點(diǎn)定義為為訪問(wèn)
把頂點(diǎn)A到自己的距離初始化為0

2.過(guò)程解析

//頂點(diǎn)探索函數(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)
找到最短頂點(diǎn)A
遍歷A到其他頂點(diǎn)的距離，如果和其他頂點(diǎn)有直接聯(lián)系，則判斷A到其他頂點(diǎn)的距離，是否是A目前到X頂點(diǎn)的距離 + X到新頂點(diǎn)的距離 < A新頂點(diǎn)的距離
如果小于，則更新到該頂點(diǎn)最短距離

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

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

第二次循環(huán)
找到最短的那個(gè)邊，除A以外 所以探索B點(diǎn)
遍歷發(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 ]

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

這就是js實(shí)現(xiàn)Dijkstra算法的過(guò)程，有些簡(jiǎn)短，有問(wèn)題可以留言交流

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/101454.html

相關(guān)文章

  • 圖算法

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

    chavesgu 評(píng)論0 收藏0

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

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

    genedna 評(píng)論0 收藏0

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

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

    qqlcbb 評(píng)論0 收藏0

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

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

    Tecode 評(píng)論0 收藏0

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

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

    JellyBool 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<