JavaScript Dijkstra算法是一種經(jīng)典的計(jì)算最短路徑的算法，它可以在圖中尋找最短路徑，常用于路程規(guī)劃、數(shù)據(jù)路由等場景。

Dijkstra算法的核心在于使用一個(gè)優(yōu)先隊(duì)列來維護(hù)待處理的節(jié)點(diǎn)，先處理與起點(diǎn)距離最短的節(jié)點(diǎn)。整個(gè)算法分為兩個(gè)步驟：路徑初始化和每次松弛操作。下面我們通過一個(gè)小例子來介紹一下具體的實(shí)現(xiàn)。

// 構(gòu)建一個(gè)簡單的圖結(jié)構(gòu)，使用鄰接表表示
const graph = {
start: { A: 6, B: 2 },
A: { finish: 1 },
B: { A: 3, finish: 5 },
finish: {}
};
// 初始化起點(diǎn)到其他節(jié)點(diǎn)的距離
const distances = {
A: 6,
B: 2,
finish: Infinity
};
// 初始化節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
const predecessors = {
A: 'start',
B: 'start',
finish: null
};
// 建立一個(gè)優(yōu)先隊(duì)列，起點(diǎn)距離最小的放在隊(duì)首
const queue = ['B', 'A'];

上述代碼中，我們構(gòu)建了一個(gè)簡單的圖結(jié)構(gòu)，其中 start 表示起點(diǎn)，finish 表示終點(diǎn)，A、B 是中間節(jié)點(diǎn)。然后我們初始化了起點(diǎn)到其他節(jié)點(diǎn)的距離，起點(diǎn)到 A 的距離是 6，到 B 的距離是 2，到終點(diǎn)的距離是 Infinity，表示還未確定最短路徑。我們同時(shí)初始化了節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，都是起點(diǎn)。最后在建立一個(gè)優(yōu)先隊(duì)列，起點(diǎn)距離最小的放在隊(duì)首，這里起點(diǎn)到 B 的距離最小，所以 B 在隊(duì)首。

接下來，我們來看一下每次松弛操作都做了哪些事情：

while (queue.length >0) {
const node = queue.shift();
const neighbors = Object.keys(graph[node]);
for (let i = 0; i< neighbors.length; i++) {
const neighbor = neighbors[i];
const distance = distances[node] + graph[node][neighbor];
if (distance< distances[neighbor]) {
distances[neighbor] = distance;
predecessors[neighbor] = node;
queue.unshift(neighbor); // 將已處理的節(jié)點(diǎn)放回隊(duì)列
}
}
}

首先，我們?nèi)〕鲫?duì)列中距離起點(diǎn)最近的節(jié)點(diǎn)。然后我們遍歷這個(gè)節(jié)點(diǎn)的所有鄰居，計(jì)算起點(diǎn)到鄰居的距離。如果這個(gè)距離比原來的距離更小，那么就更新距離和前驅(qū)節(jié)點(diǎn)。同時(shí)，我們將已經(jīng)處理完的節(jié)點(diǎn)放回隊(duì)列，因?yàn)樗锌赡艹蔀槠渌?jié)點(diǎn)的鄰居，需要重新計(jì)算距離。

最后我們輸出起點(diǎn)到終點(diǎn)的最短路徑：

const path = ['finish'];
let lastNode = 'finish';
while (predecessors[lastNode] !== 'start') {
path.unshift(predecessors[lastNode]);
lastNode = predecessors[lastNode];
}
path.unshift('start');
console.log(path.join(' ->')); // 輸出 start ->B ->A ->finish

我們從終點(diǎn)依次向前走，直到回到起點(diǎn)。這樣我們就找到了一條從起點(diǎn)到終點(diǎn)的最短路徑。

Dijkstra算法的時(shí)間復(fù)雜度為 O(V^2)，其中 V 表示節(jié)點(diǎn)的個(gè)數(shù)。在稠密圖中，可以使用堆優(yōu)化算法將復(fù)雜度降為 O(E log V)，其中 E 表示邊的數(shù)量。無論是哪種情況，Dijkstra算法都是求解最短路徑的經(jīng)典算法之一。