Docker
Network
RxJS
Nginx
TypeScript
Data Structure And Algorithm
JavaScript
PostgreSQL
React
Git演算法筆記-代克思托演算法(Dijkstra's algorithm)
甚麼是代克思托演算法?
是由荷蘭電腦科學家艾茲赫爾·戴克斯特拉在 1956 年發現的演算法，主要用途在 尋找 Graph 內兩節點 (Vertex) 間的最短路徑 ，因此可以運用在 GPS 、傳染病路徑、交通訂票系統 (尋找最便宜的車票) 上面。
透過 JavaScript 實現- 1. 建立優先佇列 (Priority Queue)
主要透過廣度優先搜尋 (BFS) 方法解決路徑問題，並且透過 PriorityQueue 來決定每一次要拜訪節點 (選擇擁有最短路徑的節點進行拜訪) ，並計算起點->節點->節點的鄰居們整段路徑是否較先前計算的短，並紀錄再 distance 物件內。
下方程式碼呈現出簡易的優先佇列 (Priority Queue) 結構，透過 JavaScript 內建的排列函式( Array.sort, 時間複雜度 O (n log n) )，將每一階段擁有最短路徑的節點排在陣列第一位。
透過 JavaScript 實現- 2. 建立 Graph
建立一個 Weighted Graph ，儲存各節點與路徑資訊。
透過 JavaScript 實現- 3. 建立 Dijkstra function
在 WeigthedGraph Class 中建立 Dijkstra function ，並在內部建立一個稱為 node 的 PriorityQueue 用來作為下一個要拜訪節點的依據。
測試結果
假設要尋找路徑的 Graph 結構如下圖，只要了解節點的數量以及各節點之間的路徑，即可透過 Graph 內的 addVertex 以及 addEdge 建構出來，如下方程式碼。
優化 優先佇列 (Priority Queue)
由於上述的 優先佇列 (Priority Queue) 是透過 JavaScript 內的 Array.prototoype.sort 來實現，其時間複雜度為 O(n log n)，因此可以將優先佇列改寫成 Binary Heap 的形式，此時的時間複雜度可以減少為 O(log n)。