JavaScript如何实现图论算法中的最短路径问题

最短路径问题是图论领域的核心问题之一，目的是在由节点和边构成的图中，找到两个指定节点之间总权重最小的路径。在前端开发的路径规划、后端服务的网络请求路由、游戏开发的寻路逻辑等场景中都有实际应用，JavaScript作为常用的开发语言，实现这类算法需要先明确图的存储方式，再选择合适的算法逻辑。

图的常见表示方式

在JavaScript中实现最短路径算法，首先需要将图的结构进行存储，常用的有两种方式：邻接矩阵和邻接表。邻接矩阵适合节点数量较少、边比较密集的图，邻接表更适合节点多、边稀疏的场景，实际开发中邻接表的使用频率更高。

邻接表的实现示例

我们可以用对象来表示邻接表，键是节点标识，值是该节点相邻节点和对应边的权重组成的数组：

// 用邻接表表示无向带权图
const graph = {
    'A': [{ node: 'B', weight: 4 }, { node: 'C', weight: 2 }],
    'B': [{ node: 'A', weight: 4 }, { node: 'C', weight: 1 }, { node: 'D', weight: 5 }],
    'C': [{ node: 'A', weight: 2 }, { node: 'B', weight: 1 }, { node: 'D', weight: 8 }, { node: 'E', weight: 10 }],
    'D': [{ node: 'B', weight: 5 }, { node: 'C', weight: 8 }, { node: 'E', weight: 2 }],
    'E': [{ node: 'C', weight: 10 }, { node: 'D', weight: 2 }]
};

Dijkstra算法实现最短路径

Dijkstra算法是求解非负权重图单源最短路径的经典算法，核心思想是每次从尚未确定最短路径的节点中，选择距离起点最近的节点，更新其相邻节点的最短距离，直到所有节点的最短距离都被确定。

算法实现步骤

• 初始化距离对象，起点距离为0，其余节点距离为无穷大
• 初始化已访问集合，记录已经确定最短路径的节点
• 循环所有节点，每次选择未访问节点中距离最小的节点
• 遍历该节点的所有相邻节点，计算经过当前节点到相邻节点的距离，若小于原有距离则更新
• 将该节点标记为已访问，重复上述步骤直到所有节点都被访问

完整代码实现

下面是JavaScript实现的Dijkstra算法完整代码，包含路径回溯的逻辑：

/**
 * Dijkstra算法求解最短路径
 * @param {Object} graph 邻接表表示的图
 * @param {string} start 起点
 * @param {string} end 终点
 * @returns {Object} 包含最短距离和路径的对象
 */
function dijkstra(graph, start, end) {
    // 初始化距离表，记录每个节点到起点的最短距离
    const distances = {};
    // 初始化前驱节点表，用于回溯路径
    const previous = {};
    // 初始化未访问节点集合
    const unvisited = new Set();

    // 初始化所有节点的距离和前驱节点
    for (const node in graph) {
        distances[node] = node === start ? 0 : Infinity;
        previous[node] = null;
        unvisited.add(node);
    }

    while (unvisited.size > 0) {
        // 找到未访问节点中距离最小的节点
        let currentNode = null;
        let minDistance = Infinity;
        for (const node of unvisited) {
            if (distances[node] < minDistance) {
                minDistance = distances[node];
                currentNode = node;
            }
        }

        // 如果最小距离是无穷大，说明剩余节点不可达，跳出循环
        if (minDistance === Infinity) break;

        // 将当前节点标记为已访问
        unvisited.delete(currentNode);

        // 如果当前节点是终点，提前结束循环
        if (currentNode === end) break;

        // 遍历当前节点的所有相邻节点
        for (const neighbor of graph[currentNode]) {
            // 计算经过当前节点到相邻节点的距离
            const newDistance = distances[currentNode] + neighbor.weight;
            // 如果新距离更小，更新距离和前驱节点
            if (newDistance < distances[neighbor.node]) {
                distances[neighbor.node] = newDistance;
                previous[neighbor.node] = currentNode;
            }
        }
    }

    // 回溯路径
    const path = [];
    let current = end;
    while (current !== null) {
        path.unshift(current);
        current = previous[current];
    }

    // 如果路径第一个节点不是起点，说明起点到终点不可达
    if (path[0] !== start) {
        return { distance: Infinity, path: [] };
    }

    return {
        distance: distances[end],
        path: path
    };
}

// 测试代码
const result = dijkstra(graph, 'A', 'E');
console.log('最短距离:', result.distance); // 输出 8
console.log('最短路径:', result.path.join(' -> ')); // 输出 A -> C -> B -> D -> E

算法注意事项

Dijkstra算法只适用于边的权重为非负值的场景，如果存在负权重的边，该算法无法得到正确结果，此时需要使用Bellman-Ford算法。另外如果图的节点数量非常多，上述基础实现的效率会比较低，可以结合优先队列优化选择最小距离节点的步骤，将时间复杂度从O(n²)降低到O((n+e)logn)，其中n是节点数，e是边数。

其他最短路径算法

除了Dijkstra算法，还有Floyd-Warshall算法可以求解任意两个节点之间的最短路径，适合节点数量较少的全源最短路径场景；A*算法则在寻路场景中加入了启发函数，能够更高效地找到目标路径，在游戏开发和地图导航中应用广泛。开发者可以根据实际的场景需求选择合适的算法实现。

JavaScript图论算法最短路径Dijkstra算法修改时间：2026-06-28 21:06:15