JS使用Dijkstra算法求解最短路徑
一、Dijkstra算法的思路
Dijkstra算法是針對單源點求最短路徑的算法。
其主要思路如下:
1. 將頂點分為兩部分:已經(jīng)知道當(dāng)前最短路徑的頂點集合Q和無法到達頂點集合R。
2. 定義一個距離數(shù)組(distance)記錄源點到各頂點的距離,下標(biāo)表示頂點,元素值為距離。源點(start)到自身的距離為0,源點無法到達的頂點的距離就是一個大數(shù)(比如Infinity)。
3. 以距離數(shù)組中值為非Infinity的頂點V為中轉(zhuǎn)跳點,假設(shè)V跳轉(zhuǎn)至頂點W的距離加上頂點V至源點的距離還小于頂點W至源點的距離,那么就可以更新頂點W至源點的距離。即下面distance[V] + matrix[V][W] < distance[W],那么distance[W] = distance[V] + matrix[V][W]。
4. 重復(fù)上一步驟,即遍歷距離數(shù)組,同時無法到達頂點集合R為空。
二、具體例子
偷個懶,直接用上一篇博客《最小生成樹算法——Prim算法和Kruskal算法的JS實現(xiàn)》的圖為例子。
它的鄰接矩陣如下:
求解步驟
第一步:假設(shè)源點為V0,那么目前最短路徑的頂點集合Q中就只有{V0}和無法到達頂點集合R中有{V1, V2, V3, V4}
第二步:初始化distance數(shù)組,就是下面這樣
第三步:以distance數(shù)組中值為非Infinity的頂點為中轉(zhuǎn)跳點,這一步就是V0,依照如果distance[V] + matrix[V][W] < distance[W],那么distance[W] = distance[V] + matrix[V][W]的規(guī)則,distance數(shù)組就會變成下面這樣,同時集合Q變成了{V0, V1, V2, V4},集合R變成了{V3}
第四步:因為集合R中還有1個頂點,所以重復(fù)第三步的方法,然后變成以V1為中轉(zhuǎn)跳點,但是以V1為中轉(zhuǎn)頂點都不滿足distance[V] + matrix[V][W] < distance[W],所以沒更新distance和兩個集合
第五步:因為集合R中還有1個頂點,所以重復(fù)第三步的方法,此時變成以V2為中轉(zhuǎn)跳點,然后發(fā)現(xiàn)V0到達V3的距離可以更新,因為2 + 3 < 9,所以distance更新,集合也更新。
之后同理,遍歷完distance之后,輸出
三、代碼實現(xiàn)
這個代碼沒有考慮權(quán)值為負數(shù)的情況,還沒驗證負數(shù)的情況,目前是按照權(quán)值為正數(shù)實現(xiàn)的,之后考慮完善。
同時這是針對單源點求最短路徑,如果求全圖各頂點的最短路徑,只需要遍歷頂點然后使用Dijkstra算法,這樣算上Dijkstra算法本身的時間復(fù)雜度,總的復(fù)雜度會是O(n^3)。
/** * Dijkstra算法:單源最短路徑 * 思路: * 1. 將頂點分為兩部分:已經(jīng)知道當(dāng)前最短路徑的頂點集合Q和無法到達頂點集合R。 * 2. 定義一個距離數(shù)組(distance)記錄源點到各頂點的距離,下標(biāo)表示頂點,元素值為距離。源點(start)到自身的距離為0,源點無法到達的頂點的距離就是一個大數(shù)(比如Infinity)。 * 3. 以距離數(shù)組中值為非Infinity的頂點V為中轉(zhuǎn)跳點,假設(shè)V跳轉(zhuǎn)至頂點W的距離加上頂點V至源點的距離還小于頂點W至源點的距離,那么就可以更新頂點W至源點的距離。即下面distance[V] + matrix[V][W] < distance[W],那么distance[W] = distance[V] + matrix[V][W]。 * 4. 重復(fù)上一步驟,即遍歷距離數(shù)組,同時無法到達頂點集合R為空。 * * @param matrix 鄰接矩陣,表示圖 * @param start 起點 * * * * 如果求全圖各頂點作為源點的全部最短路徑,則遍歷使用Dijkstra算法即可,不過時間復(fù)雜度就變成O(n^3)了 * */ function Dijkstra(matrix, start = 0) { const rows = matrix.length,//rows和cols一樣,其實就是頂點個數(shù) cols = matrix[0].length; if(rows !== cols || start >= rows) return new Error("鄰接矩陣錯誤或者源點錯誤"); //初始化distance const distance = new Array(rows).fill(Infinity); distance[start] = 0; for(let i = 0; i < rows; i++) { //達到不了的頂點不能作為中轉(zhuǎn)跳點 if(distance[i] < Infinity) { for(let j = 0; j < cols; j++) { //比如通過比較distance[i] + matrix[i][j]和distance[j]的大小來決定是否更新distance[j]。 if(matrix[i][j] + distance[i] < distance[j]) { distance[j] = matrix[i][j] + distance[i]; } } console.log(distance); } } return distance; } /** * 鄰接矩陣 * 值為頂點與頂點之間邊的權(quán)值,0表示無自環(huán),一個大數(shù)表示無邊(比如10000) * */ const MAX_INTEGER = Infinity;//沒有邊或者有向圖中無法到達 const MIN_INTEGER = 0;//沒有自環(huán) const matrix= [ [MIN_INTEGER, 9, 2, MAX_INTEGER, 6], [9, MIN_INTEGER, 3, MAX_INTEGER, MAX_INTEGER], [2, 3, MIN_INTEGER, 5, MAX_INTEGER], [MAX_INTEGER, MAX_INTEGER, 5, MIN_INTEGER, 1], [6, MAX_INTEGER, MAX_INTEGER, 1, MIN_INTEGER] ]; console.log(Dijkstra(matrix, 0));//[ 0, 5, 2, 7, 6 ]
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
- javascript算法題 求任意一個1-9位不重復(fù)的N位數(shù)在該組合中的大小排列序號
- javascript算法題:求任意一個1-9位不重復(fù)的N位數(shù)在該組合中的大小排列序號
- JavaScript求一組數(shù)的最小公倍數(shù)和最大公約數(shù)常用算法詳解【面向?qū)ο?,回歸迭代和循環(huán)】
- javascript使用遞歸算法求兩個數(shù)字組合功能示例
- JavaScript實現(xiàn)數(shù)組全排列、去重及求最大值算法示例
- javascript中解析四則運算表達式的算法和示例
- JS使用Prim算法和Kruskal算法實現(xiàn)最小生成樹
- JS實現(xiàn)計算小于非負數(shù)n的素數(shù)的數(shù)量算法示例
- JavaScript采用遞歸算法計算階乘實例
- JavaScript實現(xiàn)的一個計算數(shù)字步數(shù)的算法分享
- JS求解兩數(shù)之和算法詳解
相關(guān)文章
bootstrap3使用bootstrap datetimepicker日期插件
這篇文章主要為大家詳細介紹了bootstrap3中使用bootstrap datetimepicker日期插件的用法,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-05-05基于prototype擴展的JavaScript常用函數(shù)庫
基于prototype擴展的JavaScript常用函數(shù)庫實現(xiàn)代碼,學(xué)習(xí)js的朋友可以參考下。2010-11-11詳解Bootstrap創(chuàng)建表單的三種格式(一)
在本章中,我們將學(xué)習(xí)如何使用 Bootstrap 創(chuàng)建表單。Bootstrap 通過一些簡單的 HTML 標(biāo)簽和擴展的類即可創(chuàng)建出不同樣式的表單,對bootstrap 表單相關(guān)知識感興趣的朋友一起學(xué)習(xí)吧2016-01-01微信小程序如何實現(xiàn)radio單選框單擊打勾和取消
這篇文章主要介紹了微信小程序如何實現(xiàn)radio單選框單擊打勾和取消,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-01-01JQuery入門——用one()方法綁定事件處理函數(shù)(僅觸發(fā)一次)
one()方法功能是為所選的元素綁定一個僅觸發(fā)一次的處理函數(shù),感興趣的朋友可以了解下它的調(diào)用語法為:one(type, [data], fn),閱讀本文或許有意外的收獲呢2013-02-02ES6 proxy和reflect的使用方法與應(yīng)用實例分析
這篇文章主要介紹了ES6 proxy和reflect的使用方法,結(jié)合具體實例形式分析了ES6 proxy和reflect基本功能、原理、使用方法與操作注意事項,需要的朋友可以參考下2020-02-02