JavaScript Dijkstra算法

Dijkstra 算法是一种用于解决图论中单源最短路径问题的算法。它适用于带有非负权重的有向图或无向图。本章将详细介绍如何使用 JavaScript 来实现 Dijkstra 算法。

图的基本表示

在开始实现 Dijkstra 算法之前，我们需要了解如何在 JavaScript 中表示图。图可以使用邻接矩阵或邻接表来表示。

邻接矩阵

邻接矩阵是一个二维数组，其中每个元素表示两个节点之间是否存在边，以及该边的权重。如果节点 i 到节点 j 有一条边，则 matrix[i][j] 存储这条边的权重；否则，存储一个无穷大值（或任何表示不可达的值）。

const graph = [
    [0, 4, Infinity, Infinity, 2],
    [Infinity, 0, 3, Infinity, 10],
    [Infinity, Infinity, 0, 7, Infinity],
    [Infinity, Infinity, Infinity, 0, 5],
    [Infinity, Infinity, Infinity, Infinity, 0]
];

邻接表

邻接表是一种更节省空间的方法，尤其适合稀疏图。邻接表是通过对象或数组来存储的，其中每个键表示一个节点，其对应的值是一个数组，数组中的每个元素是一个对象，表示与该节点相连的其他节点及其权重。

const graph = {
    'A': [{ node: 'B', weight: 4 }, { node: 'E', weight: 2 }],
    'B': [{ node: 'C', weight: 3 }, { node: 'D', weight: 10 }],
    'C': [{ node: 'D', weight: 7 }],
    'D': [{ node: 'E', weight: 5 }],
    'E': []
};

Dijkstra 算法的实现步骤

Dijkstra 算法的基本思路是通过维护一个距离数组来跟踪从起点到其他所有点的最短距离，并不断更新这些距离。算法的核心在于选择当前已知最短路径的节点，然后用这个节点去更新其他节点的距离。

初始化

首先，我们需要初始化一些变量，包括距离数组、已访问节点集合等。

// www.javascriptcn.com code example
function dijkstra(graph, start) {
    const distances = {}; // 距离数组
    const visited = new Set(); // 已访问节点集合
    const unvisited = new Set(Object.keys(graph)); // 未访问节点集合

    Object.keys(graph).forEach(node => {
        if (node === start) {
            distances[node] = 0; // 起点到自身的距离为0
        } else {
            distances[node] = Infinity; // 其他节点初始距离设为无穷大
        }
    });

    return { distances, visited, unvisited };
}

查找最小距离节点

查找当前未访问节点中距离最小的那个节点，这一步是算法的核心之一。

// www.javascriptcn.com code example
function findMinDistanceNode(distances, unvisited) {
    let minNode = null;
    let minDistance = Infinity;

    for (const node of unvisited) {
        if (distances[node] < minDistance) {
            minDistance = distances[node];
            minNode = node;
        }
    }

    return minNode;
}

更新距离

一旦找到距离最小的节点，我们就可以使用它来更新其他节点的距离。

// www.javascriptcn.com code example
function updateDistances(graph, distances, visited, unvisited, currentNode) {
    for (const neighbor of graph[currentNode]) {
        if (!unvisited.has(neighbor.node)) continue;

        const newDistance = distances[currentNode] + neighbor.weight;

        if (newDistance < distances[neighbor.node]) {
            distances[neighbor.node] = newDistance;
        }
    }

    unvisited.delete(currentNode);
    visited.add(currentNode);
}

主函数

将上述功能组合在一起，形成主函数。

// www.javascriptcn.com code example
function dijkstra(graph, start) {
    const { distances, visited, unvisited } = initialize(graph, start);

    while (unvisited.size > 0) {
        const currentNode = findMinDistanceNode(distances, unvisited);
        if (currentNode === null) break;

        updateDistances(graph, distances, visited, unvisited, currentNode);
    }

    return distances;
}

// 示例
const graph = {
    'A': [{ node: 'B', weight: 4 }, { node: 'E', weight: 2 }],
    'B': [{ node: 'C', weight: 3 }, { node: 'D', weight: 10 }],
    'C': [{ node: 'D', weight: 7 }],
    'D': [{ node: 'E', weight: 5 }],
    'E': []
};

console.log(dijkstra(graph, 'A'));

应用场景和扩展

Dijkstra 算法广泛应用于各种领域，如地图导航系统、网络路由选择等。此外，通过修改算法，还可以解决更多复杂的问题，例如多源最短路径问题、动态图上的最短路径问题等。

本章介绍了如何使用 JavaScript 实现 Dijkstra 算法，包括图的基本表示方法、算法的详细步骤以及如何处理具体问题。希望读者能够理解并应用这些知识，在实际项目中有效地解决问题。