JS如何实现Dijkstra算法？优先级队列使用

Map

// 图的表示：邻接列表
const graph = {
    'A': [{ node: 'B', weight: 1 }, { node: 'C', weight: 4 }],
    'B': [{ node: 'A', weight: 1 }, { node: 'C', weight: 2 }, { node: 'D', weight: 5 }],
    'C': [{ node: 'A', weight: 4 }, { node: 'B', weight: 2 }, { node: 'D', weight: 1 }],
    'D': [{ node: 'B', weight: 5 }, { node: 'C', weight: 1 }]
};

// 优先级队列的简单实现（最小堆）
class MinPriorityQueue {
    constructor() {
        this.values = [];
    }

    // 插入元素：[值, 优先级]
    enqueue(val, priority) {
        this.values.push({ val, priority });
        this.bubbleUp();
    }

    bubbleUp() {
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            let parent = this.values[parentIdx];
            if (element.priority >= parent.priority) break;
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }

    // 提取优先级最高的元素（最小的）
    dequeue() {
        const min = this.values[0];
        const end = this.values.pop();
        if (this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }
        return min;
    }

    sinkDown() {
        let idx = 0;
        const length = this.values.length;
        const element = this.values[0];
        while (true) {
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIdx < length) {
                leftChild = this.values[leftChildIdx];
                if (leftChild.priority < element.priority) {
                    swap = leftChildIdx;
                }
            }
            if (rightChildIdx < length) {
                rightChild = this.values[rightChildIdx];
                if (
                    (swap === null && rightChild.priority < element.priority) ||
                    (swap !== null && rightChild.priority < leftChild.priority)
                ) {
                    swap = rightChildIdx;
                }
            }
            if (swap === null) break;
            this.values[idx] = this.values[swap];
            this.values[swap] = element;
            idx = swap;
        }
    }

    isEmpty() {
        return this.values.length === 0;
    }
}

function dijkstra(graph, startNode) {
    const distances = {}; // 存储从起点到每个节点的最短距离
    const previous = {};  // 存储最短路径中每个节点的前一个节点
    const pq = new MinPriorityQueue(); // 优先级队列

    // 初始化：所有距离为无穷大，起点距离为0
    for (let node in graph) {
        distances[node] = Infinity;
        previous[node] = null;
    }
    distances[startNode] = 0;

    // 将起点加入优先级队列
    pq.enqueue(startNode, 0);

    while (!pq.isEmpty()) {
        let { val: currentNode, priority: currentDistance } = pq.dequeue();

        // 如果当前取出的距离比已知的要大，说明这是个旧的、更长的路径，直接跳过
        // 这在处理图中有环或者多次入队相同节点但优先级不同时很有用
        if (currentDistance > distances[currentNode]) {
            continue;
        }

        // 遍历当前节点的所有邻居
        for (let neighbor of graph[currentNode]) {
            let neighborNode = neighbor.node;
            let weight = neighbor.weight;
            let newDistance = currentDistance + weight;

            // 如果通过当前节点到达邻居的路径更短
            if (newDistance < distances[neighborNode]) {
                distances[neighborNode] = newDistance; // 更新最短距离
                previous[neighborNode] = currentNode; // 更新前一个节点
                pq.enqueue(neighborNode, newDistance); // 将邻居加入优先级队列
            }
        }
    }

    return { distances, previous };
}

// 示例使用
const { distances, previous } = dijkstra(graph, 'A');
console.log("最短距离:", distances);
// 输出：最短距离: { A: 0, B: 1, C: 3, D: 4 }
console.log("路径前驱:", previous);
// 输出：路径前驱: { A: null, B: 'A', C: 'B', D: 'C' }

// 辅助函数：重构路径
function reconstructPath(previous, endNode) {
    const path = [];
    let currentNode = endNode;
    while (currentNode !== null) {
        path.unshift(currentNode); // 将当前节点添加到路径的开头
        currentNode = previous[currentNode]; // 追溯到前一个节点
    }
    return path;
}

console.log("从A到D的路径:", reconstructPath(previous, 'D'));
// 输出：从A到D的路径: [ 'A', 'B', 'C', 'D' ]

MinPriorityQueue

enqueue

dequeue

previous

parent

previous