JavaScript图论算法_最短路径问题-js教程-PHP中文网

JavaScript图论算法_最短路径问题

幻影之瞳

发布： 2025-11-23 22:18:06

原创

902人浏览过

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

javascript图论算法_最短路径问题

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

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

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

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

示例代码：

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  const priorityQueue = [];
<p>// 初始化距离
for (let node in graph) {
distances[node] = Infinity;
}
distances[start] = 0;
priorityQueue.push([start, 0]);</p><p>while (priorityQueue.length > 0) {
// 模拟最小堆（实际项目建议用优先队列库）
priorityQueue.sort((a, b) => a[1] - b[1]);
const [current, currentDist] = priorityQueue.shift();</p><pre class='brush:php;toolbar:false;'>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]);
  }
}

登录后复制

}

立即学习“Java免费学习笔记（深入）”；

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 算法：多源最短路径

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

BeatBot

Splash的AI音乐生成器，AI歌曲制作人！

165

查看详情

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

示例代码：

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

登录后复制

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

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

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

示例代码：

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

登录后复制