JavaScript图论算法：最短路径全解析

从现在开始，努力学习吧！本文《JavaScript图论算法：最短路径详解》主要讲解了等等相关知识点，我会在golang学习网中持续更新相关的系列文章，欢迎大家关注并积极留言建议。下面就先一起来看一下本篇正文内容吧，希望能帮到你！

最短路径问题可通过Dijkstra、Floyd-Warshall和Bellman-Ford算法解决，分别适用于单源非负权重、多源任意路径和含负权重边的场景，JavaScript适合实现这些算法用于小型图或教学演示。

最短路径问题是图论中的经典问题，目标是在加权图中找到两个节点之间的最短路径。JavaScript 可以很好地实现这些算法，适合在前端或 Node.js 环境中处理小型图结构或演示用途。以下是几种常见的最短路径算法及其 JavaScript 实现思路。

1. Dijkstra 算法：单源最短路径

Dijkstra 算法适用于带非负权重的有向或无向图，用于找出从一个起点到其他所有节点的最短距离。

核心思想： 使用优先队列（最小堆）不断选择当前距离起点最近的未访问节点，并更新其邻居的距离。

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  const priorityQueue = [];
// 初始化距离
for (let node in graph) {
distances[node] = Infinity;
}
distances[start] = 0;
priorityQueue.push([start, 0]);
while (priorityQueue.length > 0) {
// 模拟最小堆（实际项目建议用优先队列库）
priorityQueue.sort((a, b) => a[1] - b[1]);
const [current, currentDist] = priorityQueue.shift();
if (visited.has(current)) continue;
visited.add(current);

for (let neighbor in graph[current]) {
  const weight = graph[current][neighbor];
  const newDist = currentDist + weight;

  if (newDist < distances[neighbor]) {
    distances[neighbor] = newDist;
    priorityQueue.push([neighbor, newDist]);
  }
}
}
return distances;
}
// 使用示例
const graph = {
A: { B: 1, C: 4 },
B: { A: 1, C: 2, D: 5 },
C: { A: 4, B: 2, D: 1 },
D: { B: 5, C: 1 }
};
console.log(dijkstra(graph, 'A')); // 输出各点到 A 的最短距离

2. Floyd-Warshall 算法：多源最短路径

该算法计算图中任意两点之间的最短路径，适合稠密图或需要全部最短路径的情况。

特点： 支持负权重（但不能有负权环），时间复杂度为 O(n³)。

function floydWarshall(nodes, edges) {
  const dist = {};
// 初始化距离矩阵
nodes.forEach(node => {
dist[node] = {};
nodes.forEach(other => {
dist[node][other] = node === other ? 0 : Infinity;
});
});
// 添加边
edges.forEach(([u, v, w]) => {
dist[u][v] = w;
dist[v][u] = w; // 若是无向图
});
// 动态规划更新最短路径
nodes.forEach(k => {
nodes.forEach(i => {
nodes.forEach(j => {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
});
});
});
return dist;
}
// 使用示例
const nodes = ['A', 'B', 'C', 'D'];
const edges = [
['A', 'B', 1],
['B', 'C', 2],
['C', 'D', 1],
['A', 'D', 5]
];
console.log(floydWarshall(nodes, edges));

3. Bellman-Ford 算法：支持负权重边

Bellman-Ford 可处理包含负权重边的图，并能检测负权环。

适用场景： 边中有负数，且图不大。

function bellmanFord(edges, nodes, start) {
  const dist = {};
  nodes.forEach(node => {
    dist[node] = Infinity;
  });
  dist[start] = 0;
// 松弛操作 |V| - 1 次
for (let i = 0; i < nodes.length - 1; i++) {
for (let [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// 检测负权环
for (let [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
throw new Error("图中存在负权环");
}
}
return dist;
}

4. 如何选择合适的算法？

根据图的特点和需求选择：

• 单源、非负权重 → Dijkstra
• 任意两点最短路径 → Floyd-Warshall
• 含负权重边 → Bellman-Ford
• 稀疏图优先考虑 Dijkstra + 堆优化
• 需要路径记录时，可在更新距离时同步记录前驱节点

基本上就这些。JavaScript 虽不是高性能计算首选，但在教学、原型开发或小型应用中足够使用。关键是理解每种算法的适用边界和实现逻辑。

今天关于《JavaScript图论算法：最短路径全解析》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！