在图论中，最短路径算法是一类重要的算法，用于求解从一个顶点到图中其他所有顶点的最短路径。本文将详细介绍两种经典的最短路径算法：Dijkstra算法和Bellman-Ford算法，探讨它们的原理、应用场景及实现细节。
Dijkstra算法是由荷兰计算机科学家Edsger Dijkstra于1956年提出的，适用于求解加权图中单源最短路径问题，其中加权图中的边权重为非负值。
Dijkstra算法的核心思想是逐步扩展最短路径集合。算法从一个源顶点开始，通过逐步选择当前最短路径集合中距离源顶点最近的顶点，更新其邻居顶点的最短路径值，直到所有顶点都被包含在最短路径集合中。
function dijkstra(graph, source) {
let dist = new Array(graph.length).fill(Infinity);
dist[source] = 0;
let Q = new MinHeap(); // 假设有一个最小堆的实现
Q.insert(source, 0);
while (!Q.isEmpty()) {
let [u, d] = Q.extractMin();
if (d > dist[u]) continue;
for (let [v, weight] of graph[u]) {
let alt = dist[u] + weight;
if (alt < dist[v]) {
dist[v] = alt;
Q.insert(v, alt);
}
}
}
return dist;
}
Bellman-Ford算法是由美国计算机科学家Leonard Bellman和Vernon Ford于1956年提出的，同样适用于求解单源最短路径问题，但其特点是可以处理含有负权重边的图。
Bellman-Ford算法的基本思想是逐步松弛所有边，即不断检查通过某个顶点是否能使另一条边的路径更短。由于图中任意两个顶点之间最短路径的长度不会超过图中的顶点数减一，因此通过V-1次松弛操作可以保证找到所有顶点的最短路径。
function bellmanFord(graph, source) {
let dist = new Array(graph.length).fill(Infinity);
dist[source] = 0;
for (let i = 0; i < graph.length - 1; i++) {
for (let [u, neighbors] of graph.entries()) {
for (let [v, weight] of neighbors) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
}
// 检测负权重环
for (let [u, neighbors] of graph.entries()) {
for (let [v, weight] of neighbors) {
if (dist[u] + weight < dist[v]) {
throw new Error("Graph contains a negative-weight cycle");
}
}
}
return dist;
}
Dijkstra算法和Bellman-Ford算法是解决图论中最短路径问题的经典算法。Dijkstra算法适用于边权重为非负的图，通过优先队列优化可以高效运行；而Bellman-Ford算法则可以处理含有负权重边的图，并且能够检测负权重环。在实际应用中，根据具体问题的需求选择合适的算法，是实现高效路径优化的关键。