摘要:算法系列單源最短路徑算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于年提出的,因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法,解決的是有向圖中最短路徑問題。
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算法的過程,有些簡短,有問題可以留言交流
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/101454.html
摘要:面試算法實踐與國外大廠習題指南翻譯自維護的倉庫,包含了在線練習算法概述與大廠習題實戰等內容。面試算法實踐與國外大廠習題指南在線練習在線面試編程數據結構鏈表即是由節點組成的線性集合,每個節點可以利用指針指向其他節點。 面試算法實踐與國外大廠習題指南 翻譯自 Kevin Naughton Jr. 維護的倉庫 interviews,包含了在線練習、算法概述與大廠習題實戰等內容。筆者發現正好和...
摘要:鄰接矩陣在鄰接矩陣實現中,由行和列都表示頂點,由兩個頂點所決定的矩陣對應元素表示這里兩個頂點是否相連如果相連這個值表示的是相連邊的權重。直到返回到頂點完成探索具體還有版的深度和廣度優先的算法,具體代碼奉上直達地址 圖github直達地址 https://github.com/fanshyiis/... 在計算機科學中,一個圖就是一些頂點的集合,這些頂點通過一系列邊結對(連接)。頂點用圓...
摘要:學習資料迪杰斯特拉計算的是單源最短路徑,而弗洛伊德計算的是多源最短路徑代碼不能設置為,否則兩個相加會溢出導致出現負權創建頂點和邊 學習資料 迪杰斯特拉計算的是單源最...
閱讀 2951·2023-04-26 01:52
閱讀 3477·2021-09-04 16:40
閱讀 3635·2021-08-31 09:41
閱讀 1768·2021-08-09 13:41
閱讀 569·2019-08-30 15:54
閱讀 2968·2019-08-30 11:22
閱讀 1619·2019-08-30 10:52
閱讀 954·2019-08-29 13:24