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

SoapEye 發布于2019-08-23 15:04 / 1525人閱讀

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

Javascript算法系列 - 單源最短路徑 - Dijkstra算法

迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于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: 鄰接矩陣的意思是：用一個二數組表示個頂點間的關系，來確定各頂點間的關系，因為圖為有向圖，所以上圖的鄰接矩陣如上

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

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.初始化數據
定義 dist 數組來儲存當前A頂點到其它各個頂點間的距離
定義 visited 數組來儲存ABCDEF頂點是否被訪問過，以免重復訪問，形成環
定義 length 來儲存所有頂點的數量
定義 INF 為javascript的最大整數 Number.MAX_SAFE_INTEGER

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

初始化dist visted 數組，把所有頂點距離初始化為無限大，所有頂點定義為為訪問
把頂點A到自己的距離初始化為0

2.過程解析

//頂點探索函數
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]
      }
    }
  }

//尋找最短路徑函數
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
}

具體探索邏輯如下

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

第一次循環完后相應輸出值
發現A
遍歷發現A -> B為2 A->C為4 均小于無窮大，所以更新A點到B，C的最短距離

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

第二次循環
找到最短的那個邊，除A以外所以探索B點
遍歷發現 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實現Dijkstra算法的過程，有些簡短，有問題可以留言交流

云服務器 GPU云服務器最短路算法dijkstra 最短路徑算法程序最短路徑算法大全最短路徑算法合集

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/101454.html

圖算法

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

chavesgu 2019-08-19 10:29 評論0 收藏0
面試算法實踐與國外大廠習題指南

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

genedna 2019-08-14 17:46 評論0 收藏0
【你該懂一點Javascript算法系列】之【圖類】的定義及深度優先與廣度優先搜索算法

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

qqlcbb 2019-08-23 15:17 評論0 收藏0
最短路徑算法總結

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

Tecode 2022-06-28 19:00 評論0 收藏0
【程序員必會十大算法】之弗洛伊德算法

摘要：學習資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設置為，否則兩個相加會溢出導致出現負權創建頂點和邊學習資料迪杰斯特拉計算的是單源最...

JellyBool 2021-09-30 09:47 評論0 收藏0