一篇文章讲透Dijkstra最短路径算法

Dijkstra算法是解决单源最短路径问题的一种经典算法，其时间复杂度为O(n^2)，其中n为节点数。该算法是由荷兰计算机科学家Edsger W. Dijkstra于1959年提出的。本文将从算法流程、实现方法及案例说明三个方面详细介绍Dijkstra算法。

一、算法流程

1. 初始化。将起点的距离赋为0，其余节点的距离赋为正无穷大。

2. 将起点加入已访问集合中。

3. 遍历起点所有相邻节点，并更新它们的距离。

4. 从未访问的节点集合中选出距离起点最近的节点，将其加入已访问集合中。

5. 重复步骤3和4，直到所有节点都被加入已访问集合中或者不存在未访问的节点。

6. 最短路径即为初始化起点到终点的距离。

二、实现方法

Dijkstra算法可以通过邻接矩阵或邻接表来实现。在基于邻接矩阵的实现中，需要使用二维数组来表示图，其中matrix[i][j]表示节点i到节点j的距离。在基于邻接表的实现中，需要使用链表来表示每个节点的所有相邻节点及其距离。

对于邻接矩阵的实现，伪代码如下：

```

void dijkstra(int *matrix, int n, int start, int *distance) {

bool visited[n] = {false}; // 记录是否访问过该节点

distance[start] = 0; // 起点到自己的距离为0

// 遍历所有节点

for (int i = 0; i < n - 1; i++) {

int min_distance = INT_MAX; // 初始化最小距离为正无穷大

int min_index = -1; // 记录距离起点最近的节点编号

// 找出距离起点最近的未访问节点

for (int j = 0; j < n; j++) {

if (!visited[j] && distance[j] < min_distance) {

min_distance = distance[j];

min_index = j;

}

}

visited[min_index] = true; // 将最近节点加入已访问集合中

// 更新起点到所有未访问节点的距离

for (int j = 0; j < n; j++) {

if (!visited[j] && matrix[min_index][j] != INT_MAX) { // 未访问过且存在连接

int new_distance = min_distance + matrix[min_index][j]; // 更新距离

if (new_distance < distance[j]) {

distance[j] = new_distance;

}

}

}

}

}

```

对于邻接表的实现，伪代码如下：

```

void dijkstra(vector> *adj_list, int n, int start, int *distance) {

bool visited[n] = {false}; // 记录是否访问过该节点

distance[start] = 0; // 起点到自己的距离为0

// 遍历所有节点

for (int i = 0; i < n - 1; i++) {

int min_distance = INT_MAX; // 初始化最小距离为正无穷大

int min_index = -1; // 记录距离起点最近的节点编号

// 找出距离起点最近的未访问节点

for (int j = 0; j < n; j++) {

if (!visited[j] && distance[j] < min_distance) {

min_distance = distance[j];

min_index = j;

}

}

visited[min_index] = true; // 将最近节点加入已访问集合中

// 更新起点到所有未访问节点的距离

for (auto it = adj_list[min_index].begin(); it != adj_list[min_index].end(); it++) {

int j = it->first;

int weight = it->second;

if (!visited[j]) { // 未访问过

int new_distance = min_distance + weight; // 更新距离

if (new_distance < distance[j]) {

distance[j] = new_distance;

}

}

}

}

}

```

三、案例说明

以下是一个简单的例子，说明如何使用Dijkstra算法求解从起点A到终点D的最短路径。

假设有如下图所示的无向有权图。


使用邻接矩阵表示，其矩阵如下：

```

0 10 INF 5 INF

10 0 1 2 INF

INF 1 0 1 4

5 2 1 0 2

INF INF 4 2 0

```

使用Dijkstra算法，从起点A开始搜索。经过计算后，得到A到各节点的最短路径：

```

A -> A: 0

A -> B: 10

A -> C: 9

A -> D: 5

A -> E: INF

```

因为从A到E的距离为正无穷大，所以A无法到达E节点。最终，从A到D的最短路径为A -> B -> D，距离为15。

四、总结

本文详细讲解了Dijkstra算法的流程、实现方法及案例说明。Dijkstra算法是解决单源最短路径问题的一种经典算法，虽然其时间复杂度较高，但在实际应用中仍有广泛的使用。 如果你喜欢我们三七知识分享网站的文章， 欢迎您分享或收藏知识分享网站文章 欢迎您到我们的网站逛逛喔！https://www.37seo.cn/