查找节点之间的最短路径

演示如何使用寻路算法查找并突出显示两个节点之间的最短路径。

查找节点之间的最短路径

功能概述

此示例演示如何使用寻路算法查找并突出显示图中两个节点之间的最短路径。

核心特性实现

寻路算法

实现 BFS 或 Dijkstra 算法以查找最短路径：

const findMinPath = (startId: string, endId: string): string[] => {
    const visited = new Set<string>();
    const queue: { nodeId: string; path: string[] }[] = [
        { nodeId: startId, path: [startId] }
    ];

    while (queue.length > 0) {
        const { nodeId, path } = queue.shift()!;
        if (nodeId === endId) return path;

        if (visited.has(nodeId)) continue;
        visited.add(nodeId);

        const neighbors = getNeighbors(nodeId);
        for (const neighbor of neighbors) {
            queue.push({ nodeId: neighbor.id, path: [...path, neighbor.id] });
        }
    }
    return [];
};

高亮路径

可视化找到的路径：

const highlightPath = (path: string[]) => {
    const allNodes = graphInstance.getNodes();
    const allLines = graphInstance.getLines();

    allNodes.forEach(node => {
        const isInPath = path.includes(node.id);
        graphInstance.updateNode(node, {
            opacity: isInPath ? 1 : 0.2,
            color: isInPath ? '#43a2f1' : undefined
        });
    });

    allLines.forEach(line => {
        const isInPath = path.includes(line.from) && path.includes(line.to) &&
            isConsecutiveInPath(path, line.from, line.to);
        graphInstance.updateLine(line, {
            color: isInPath ? '#43a2f1' : '#cccccc',
            lineWidth: isInPath ? 3 : 1
        });
    });
};

路径选择

允许用户选择起点和终点：

let selectedNodes: string[] = [];

const onNodeClick = (node: RGNode) => {
    selectedNodes.push(node.id);
    if (selectedNodes.length === 2) {
        const path = findMinPath(selectedNodes[0], selectedNodes[1]);
        highlightPath(path);
        selectedNodes = [];
    }
};

创意使用场景

• 网络分析：在网络中查找最佳路由
• 社交网络：人员之间的最短连接
• 交通：路线规划和优化
• 供应链：优化物流路径
• 游戏开发：AI 角色的寻路