最短路径问题可通过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]);
}
}
}
立即学习“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 算法：多源最短路径
该算法计算图中任意两点之间的最短路径，适合稠密图或需要全部最短路径的情况。
特点： 支持负权重（但不能有负权环），时间复杂度为 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 虽不是高性能计算首选，但在教学、原型开发或小型应用中足够使用。关键是理解每种算法的适用边界和实现逻辑。
