实际上，Dijkstra 算法在现实生活中有很多应用，它的思想：在图中的两点，算出最短路径，即花费最小的开销，具备很有价值的现实意义。
很多事都能抽象，算清楚每个节点的联系，从上一个节点到下一个节点的开销，最终抵达结果节点，计算整个成本。这个过程无疑是在对信息作最有效的规整、最有效率的利用。
回顾
首先，我们来回顾一下这个经典的算法。
其实很简单：Dijkstra 核心思想是不断地寻找最“近”的未访问节点，并更新其他节点到起点的最短距离。
将以上这句话可以拆解为 4 个步骤：
- 初始化：将所有节点的最短路径估计设为无限大，只有起点的距离设为0。
- 选择最近的节点：从未访问的节点中找到距离起点最近的节点。
- 更新邻居节点的距离：检查这个节点的所有邻居，如果通过这个节点到达邻居的距离比当前记录的距离短，就更新这个距离。
- 重复：重复第2和第3步，直到访问了所有的节点。
之前的算法解释：
应用
Dijkstra 算法不只是理论上的玩具算法，它在计算机科学、网络技术、甚至日常生活中都有广泛的应用~
本篇就是来看看一个具体的算法落地场景实践：
网络路由：保证数据包的快速传递
假设有一个小型企业网络，包含四个节点（A, B, C, D），节点之间的连接及其带宽（或权重）如下图所示。我们的任务是找到从A到D的最快路径，确保数据包快速传递。
A到B的带宽为10Mbps；A到C的带宽为15Mbps；B到D的带宽为10Mbps；C到B的带宽为5Mbps；C到D的带宽为20Mbps
用 JS 对象形成一个关系矩阵：
代码语言：javascript复制const graph = {
A: {B: 10, C: 15},
B: {D: 10},
C: {B: 5, D: 20},
D: {}
};然后定义一个优先队列，用于支持Dijkstra算法中的节点选择。
DijkstraJS 函数实现：
// 定义优先队列类
class PriorityQueue {
constructor() {
this.nodes = [];
}
enqueue(priority, key) {
this.nodes.push({ key, priority });
this.sort();
}
dequeue() {
return this.nodes.shift();
}
sort() {
this.nodes.sort((a, b) => a.priority - b.priority);
}
isEmpty() {
return !this.nodes.length;
}
}
function dijkstra(graph, start, goal) {
let distances = {};
let previous = {};
let queue = new PriorityQueue();
// 初始化所有节点的距离为无限大，起点的距离为0
for (let vertex in graph) {
distances[vertex] = vertex === start ? 0 : Infinity;
queue.enqueue(distances[vertex], vertex);
}
while (!queue.isEmpty()) {
let smallest = queue.dequeue().key;
// 如果达到目标节点，则构建并返回路径
if (smallest === goal) {
let path = [];
while (previous[smallest]) {
path.push(smallest);
smallest = previous[smallest];
}
return path.concat(start).reverse();
}
// 遍历所有邻接节点，更新距离和前置节点
for (let neighbor in graph[smallest]) {
let alt = distances[smallest] graph[smallest][neighbor];
if (alt < distances[neighbor]) {
distances[neighbor] = alt;
previous[neighbor] = smallest;
queue.enqueue(alt, neighbor);
}
}
}
// 如果没有找到路径，则返回空数组
return [];
}
// 定义网络图
const graph = {
A: { B: 10, C: 15 },
B: { D: 10 },
C: { B: 5, D: 20 },
D: {}
};
// 使用Dijkstra算法寻找从A到D的最短路径
const fastestPath = dijkstra(graph, 'A', 'D');
console.log(fastestPath); // 应该输出: ['A', 'C', 'D']思路是：
首先，所有节点的最短路径估计都被设置为无限大。
处理节点A： 从队列中移除A（因为它是距离最短的节点），并考虑它的所有邻居（B和C）。 更新到达B和C的距离。A到B的带宽为10，A到C的带宽为15。因此，A到B的距离更新为10，A到C的距离更新为15。
下一个距离最短的节点是B（距离为10），从队列中移除B，并考虑它的邻居D。 更新到达D的距离。从A经B到D的总带宽为20（A到B为10，B到D为10），因此A到D的距离更新为20。
接着考虑C（距离为15），更新它的邻居B和D的距离。 但是，从A经C到B的总带宽为20，比已知的A到B的距离（10）要大，因此不更新A到B的距离。
从A经C到D的总带宽为35，比已知的A到D的距离（20）要大，因此也不更新A到D的距离。
所有节点都被处理完毕，完成处理，从A到B再到D这条路径的总带宽（或“成本”）更低~
步骤 | A | B | C | D |
|---|---|---|---|---|
初始化 | 无限大 | 无限大 | 无限大 | 无限大 |
处理节点A | 0 | 10 (A->B) | 15 (A->C) | 无限大 |
处理节点B | 0 | 10 | 15 (A->C) | 20 (A->B->D) |
处理节点C | 0 | 10 | 15 | 20 |
完成 | 0 | 10 | 15 | 20 |
小结
除了数据传输更快，当然还有相应的场景落地：导航-路径最快、游戏中达成任务步骤最快、城市交通中路线规划最短/最不堵等等问题中都能用到它，是不能错过的“算法利器”！
