17.Dijkstra 算法：OSPF 路由的核心最短路径算法

一、什么是 Dijkstra 算法？

Dijkstra 算法是一种单源最短路径算法，由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年提出。它的核心思想是从起点出发，每次选择距离起点最近的未访问节点，更新其邻居节点的距离，直到所有节点都被访问，最终得到起点到所有其他节点的最短路径。

简单来说，Dijkstra 算法就像 “找最短路线的导航”：

• 你在起点，要去多个目的地；
• 每次先去离你最近的地方，然后从那里出发更新其他地方的距离；
• 重复这个过程，直到所有地方的最短距离都算出来。

二、Dijkstra 算法的核心步骤

Dijkstra 算法的核心步骤可以分为以下几步：

三、Dijkstra 算法的代码实现

1. Python 版本（直观易懂）

import heapq

def dijkstra(graph, start):
# 初始化距离：所有节点距离设为无穷大
distances = {node: float('inf') for node in graph}
distances[start] = 0

# 优先队列：存储（距离，节点），距离小的优先
priority_queue = []
heapq.heappush(priority_queue, (0, start))

# 记录路径
path = {node: None for node in graph}

while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)

# 如果当前距离大于已知最短距离，跳过
if current_distance > distances[current_node]:
continue

# 遍历邻居
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight

# 如果新距离更短，更新
if distance < distances[neighbor]:
distances[neighbor] = distance
path[neighbor] = current_node
heapq.heappush(priority_queue, (distance, neighbor))

return distances, path

# 测试：路由器网络
graph = {
'R1': {'R2': 1, 'R3': 10, 'R5': 10},
'R2': {'R1': 1, 'R3': 3, 'R5': 2},
'R3': {'R1': 10, 'R2': 3, 'R4': 1},
'R4': {'R3': 1, 'R5': 1},
'R5': {'R1': 10, 'R2': 2, 'R4': 1}
}

distances, path = dijkstra(graph, 'R1')
print("最短距离：", distances)
print("路径：", path)

2. C 语言版本（更贴近底层）

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define INF INT_MAX
#define N 5 // 路由器数量

// 路由器名称
char nodes[] = {'R1', 'R2', 'R3', 'R4', 'R5'};

// 图的邻接矩阵
int graph[N][N] = {
{0, 1, 10, INF, 10},
{1, 0, 3, INF, 2},
{10, 3, 0, 1, INF},
{INF, INF, 1, 0, 1},
{10, 2, INF, 1, 0}
};

// 找到距离最小的未访问节点
int minDistance(int dist[], int visited[]) {
int min = INF, min_index;
for (int v = 0; v < N; v++) {
if (visited[v] == 0 && dist[v] < min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}

// Dijkstra算法
void dijkstra(int start) {
int dist[N]; // 存储最短距离
int visited[N]; // 标记是否已访问
int path[N]; // 记录路径

// 初始化
for (int i = 0; i < N; i++) {
dist[i] = INF;
visited[i] = 0;
path[i] = -1;
}
dist[start] = 0;

for (int count = 0; count < N – 1; count++) {
// 选择距离最小的未访问节点
int u = minDistance(dist, visited);
visited[u] = 1;

// 更新邻居的距离
for (int v = 0; v < N; v++) {
if (!visited[v] && graph[u][v] != INF && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
path[v] = u;
}
}
}

// 打印结果
printf("起点：%c\\n", nodes[start]);
for (int i = 0; i < N; i++) {
printf("到%c的最短距离：%d，路径：", nodes[i], dist[i]);
int p = i;
while (p != -1) {
printf("%c ", nodes[p]);
p = path[p];
}
printf("\\n");
}
}

int main() {
dijkstra(0); // 从R1出发
return 0;
}

四、Dijkstra 算法的特点

• 时间复杂度：O (n²)（朴素实现），O (m log n)（优先队列实现）；
• 空间复杂度：O (n)，需要存储距离和访问标记；
• 适用场景：边权非负的图，不能处理负权边；
• 单源最短路径：只能计算起点到所有其他节点的最短路径。

五、Dijkstra 算法的优化

为了提高 Dijkstra 算法的效率，可以进行以下优化：

六、Dijkstra 算法的实际应用场景

Dijkstra 算法是一种非常基础且重要的算法，常见场景包括：

七、Dijkstra 算法 vs BFS

Dijkstra 算法和 BFS 都是路径搜索算法，它们的区别如下：

八、总结

Dijkstra 算法是一种单源最短路径算法，它通过每次选择距离起点最近的未访问节点，更新其邻居节点的距离，最终得到起点到所有其他节点的最短路径。

Dijkstra 算法是 OSPF 路由协议的核心算法，广泛应用于导航系统、网络设计、游戏 AI 等领域，是一种非常基础且重要的算法。

希望这篇文章能帮助你理解 Dijkstra 算法的原理和实现！