Dijkstra 算法在网络路由的应用

掘金安东尼

发布于 2023-12-18 11:32:27

1720

发布于 2023-12-18 11:32:27

文章被收录于专栏：掘金安东尼掘金安东尼

实际上，Dijkstra 算法在现实生活中有很多应用，它的思想：在图中的两点，算出最短路径，即花费最小的开销，具备很有价值的现实意义。

很多事都能抽象，算清楚每个节点的联系，从上一个节点到下一个节点的开销，最终抵达结果节点，计算整个成本。这个过程无疑是在对信息作最有效的规整、最有效率的利用。

回顾

首先，我们来回顾一下这个经典的算法。

其实很简单：Dijkstra 核心思想是不断地寻找最“近”的未访问节点，并更新其他节点到起点的最短距离。

将以上这句话可以拆解为 4 个步骤：

初始化：将所有节点的最短路径估计设为无限大，只有起点的距离设为0。
选择最近的节点：从未访问的节点中找到距离起点最近的节点。
更新邻居节点的距离：检查这个节点的所有邻居，如果通过这个节点到达邻居的距离比当前记录的距离短，就更新这个距离。
重复：重复第2和第3步，直到访问了所有的节点。

之前的算法解释：

应用

Dijkstra 算法不只是理论上的玩具算法，它在计算机科学、网络技术、甚至日常生活中都有广泛的应用~

本篇就是来看看一个具体的算法落地场景实践：

网络路由：保证数据包的快速传递

假设有一个小型企业网络，包含四个节点（A, B, C, D），节点之间的连接及其带宽（或权重）如下图所示。我们的任务是找到从A到D的最快路径，确保数据包快速传递。

A到B的带宽为10Mbps；A到C的带宽为15Mbps；B到D的带宽为10Mbps；C到B的带宽为5Mbps；C到D的带宽为20Mbps

用 JS 对象形成一个关系矩阵：

const graph = {
    A: {B: 10, C: 15},
    B: {D: 10},
    C: {B: 5, D: 20},
    D: {}
};

然后定义一个优先队列，用于支持Dijkstra算法中的节点选择。

DijkstraJS 函数实现：

// 定义优先队列类
class PriorityQueue {
    constructor() {
        this.nodes = [];
    }

    enqueue(priority, key) {
        this.nodes.push({ key, priority });
        this.sort();
    }

    dequeue() {
        return this.nodes.shift();
    }

    sort() {
        this.nodes.sort((a, b) => a.priority - b.priority);
    }

    isEmpty() {
        return !this.nodes.length;
    }
}

function dijkstra(graph, start, goal) {
    let distances = {};
    let previous = {};
    let queue = new PriorityQueue();

    // 初始化所有节点的距离为无限大，起点的距离为0
    for (let vertex in graph) {
        distances[vertex] = vertex === start ? 0 : Infinity;
        queue.enqueue(distances[vertex], vertex);
    }

    while (!queue.isEmpty()) {
        let smallest = queue.dequeue().key;

        // 如果达到目标节点，则构建并返回路径
        if (smallest === goal) {
            let path = [];
            while (previous[smallest]) {
                path.push(smallest);
                smallest = previous[smallest];
            }
            return path.concat(start).reverse();
        }

        // 遍历所有邻接节点，更新距离和前置节点
        for (let neighbor in graph[smallest]) {
            let alt = distances[smallest] + graph[smallest][neighbor];
            if (alt < distances[neighbor]) {
                distances[neighbor] = alt;
                previous[neighbor] = smallest;
                queue.enqueue(alt, neighbor);
            }
        }
    }

    // 如果没有找到路径，则返回空数组
    return [];
}

// 定义网络图
const graph = {
    A: { B: 10, C: 15 },
    B: { D: 10 },
    C: { B: 5, D: 20 },
    D: {}
};

// 使用Dijkstra算法寻找从A到D的最短路径
const fastestPath = dijkstra(graph, 'A', 'D');
console.log(fastestPath); // 应该输出: ['A', 'C', 'D']

思路是：

首先，所有节点的最短路径估计都被设置为无限大。

处理节点A：从队列中移除A（因为它是距离最短的节点），并考虑它的所有邻居（B和C）。更新到达B和C的距离。A到B的带宽为10，A到C的带宽为15。因此，A到B的距离更新为10，A到C的距离更新为15。

下一个距离最短的节点是B（距离为10），从队列中移除B，并考虑它的邻居D。更新到达D的距离。从A经B到D的总带宽为20（A到B为10，B到D为10），因此A到D的距离更新为20。

接着考虑C（距离为15），更新它的邻居B和D的距离。但是，从A经C到B的总带宽为20，比已知的A到B的距离（10）要大，因此不更新A到B的距离。

从A经C到D的总带宽为35，比已知的A到D的距离（20）要大，因此也不更新A到D的距离。

所有节点都被处理完毕，完成处理，从A到B再到D这条路径的总带宽（或“成本”）更低~

步骤	A	B	C	D
初始化	无限大	无限大	无限大	无限大
处理节点A	0	10 (A->B)	15 (A->C)	无限大
处理节点B	0	10	15 (A->C)	20 (A->B->D)
处理节点C	0	10	15	20
完成	0	10	15	20