function dijkstra(graph, start, finish) {
const distances = {};
const previous = {};
const visited = new Set();
const nodes = Object.keys(graph);
// 初始化距离和前驱节点
for (let node of nodes) {
distances[node] = Infinity;
previous[node] = null;
}
distances[start] = 0;
// 循环直到找到最短路径
while (nodes.length) {
let currentNode = findClosestNode(nodes, distances, visited);
if (currentNode === finish) break; // 找到最短路径
visited.add(currentNode);
// 更新当前节点的邻居节点的距离
for (let neighbor in graph[currentNode]) {
if (visited.has(neighbor)) continue;
let newDistance = distances[currentNode] + graph[currentNode][neighbor];
if (newDistance < distances[neighbor]) {
distances[neighbor] = newDistance;
previous[neighbor] = currentNode;
}
}
}
// 构建最短路径
const buildPath = (prev, node) => {
if (prev[node] && prev[node] !== start) {
return buildPath(prev, prev[node]) + '->' + node;
} else {
return node;
}
};
return {
distances: distances,
path: buildPath(previous, finish)
};
}
// 测试用例
const graph = {
'start': {'a': 6, 'b': 2},
'a': {'finish': 1},
'b': {'a': 3, 'finish': 5},
'finish': {}
};
const shortestPath = dijkstra(graph, 'start', 'finish');
console.log(shortestPath.distances);
console.log('Shortest Path:', shortestPath.path);这段代码实现了Dijkstra算法，用于找到加权图中两个节点之间的最短路径。它首先初始化距离和前驱节点，然后通过循环找到最短路径，并构建最短路径的路径字符串。