JS使用dijkstra算法实现查找最短路径

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算法，用于找到加权图中两个节点之间的最短路径。它首先初始化距离和前驱节点，然后通过循环找到最短路径，并构建最短路径的路径字符串。