小熊の小站

Try my best.

图的遍历与Dijkstra最短路算法实现

Littlebear0729's Avatar 2022-05-21 学习记

  1. 1. 0 概述
  2. 2. 1 实验设计
    1. 2.1. 1.1 算法实现原理
    2. 2.2. 1.2 算法设计与分析
      1. 2.2.1. DFS深度优先搜索
      2. 2.2.2. BFS广度优先搜索
      3. 2.2.3. Dijkstra最短路算法
  3. 3. 2 实验结果说明与分析
    1. 3.1. BFS与DFS
    2. 3.2. Dijkstra最短路算法

0 概述

本实验使用C++语言实现了图的遍历与Dijkstra最短路算法,使用邻接表存储图。

1 实验设计

1.1 算法实现原理

定义n为顶点数,m为边数。

定义二维可变数组graph[u][v],其中u、v为顶点,代表 u -> v 有一条边,边权为w。

1
vector<vector<int>> graph;

1.2 算法设计与分析

定义数组vis[u],其中u为顶点,代表u是否被访问过。

1
vector<bool> vis;

DFS深度优先搜索

从起点顶点u开始,递归遍历这个点的所有邻接点。

当遍历到这个点的时候,标记该点为已访问,直到所有点都被访问后,遍历结束。

1
2
3
4
5
6
7
8
9
10
11
void dfs(int u) {
if (vis[u]) return;
printf("%d ", u);
vis[u] = true;
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if (!vis[v]) {
dfs(v);
}
}
}

BFS广度优先搜索

从起点顶点开始,遍历这个点的所有邻接点。

每遍历一个点,将该点的所有邻接点加入队列,标记该点为已访问,直到队列为空,遍历结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bfs(int u) {
printf("%d ", u);
vis[u] = true;
queue<int> q;
q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if (!vis[v]) {
printf("%d ", v);
vis[v] = true;
q.push(v);
}
}
}
}

Dijkstra最短路算法

在实现Dijkstra最短路算法的过程中,创建了一个结构体edge,其中v是边的终点,w是边的权重。

1
2
3
struct edge {
int v, w; // v: 终点, w: 权重
};

每次通过遍历,找到一条没有被访问过的距离最小的顶点,对这个点的所有邻接点更新距离为可能的最短距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dijkstra(int s) {
dis[s] = 0;
for (int i = 1; i <= n; i++) {
int u = -1, min = INF;
// 找到未访问的、距离最小的顶点
for (int j = 1; j <= n; j++) {
if (!vis[j] && dis[j] < min) {
u = j;
min = dis[j];
}
}
if (u == -1) break;
vis[u] = true;
// 更新距离(松弛)
for (int j = 0; j < graph[u].size(); j++) {
int v = graph[u][j].v;
int w = graph[u][j].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
}
}
}
}

2 实验结果说明与分析

BFS与DFS

第一行输入点和边的数量。

接下来每行为一条边的信息,其中第一个数字为起点,第二个数字为终点。

输入如下:

1
2
3
4
5
6
7
8
9
10
11
5 10
1 2
1 3
2 3
3 2
2 4
3 4
3 5
4 5
5 4
5 1

经过DFS和BFS遍历后,输出结果如下:

1
2
1 2 3 4 5
1 2 3 4 5

代码在homework3/graph.cpp

Dijkstra最短路算法

第一行输入点和边的数量。

接下来每行为一条边的信息,其中第一个数字为起点,第二个数字为终点,第三个数字为边权。

输入如下:

1
2
3
4
5
6
7
8
9
10
11
5 10
1 2 10
1 3 5
2 3 2
3 2 3
2 4 1
3 4 9
3 5 2
4 5 4
5 4 6
5 1 7

输出起点(点1)到其他所有点的最短距离。

通过更改函数参数,可以设定任意一个起点。

输出如下:

1
2
3
4
5
node 1 to 1: minimum weight is 0
node 1 to 2: minimum weight is 8
node 1 to 3: minimum weight is 5
node 1 to 4: minimum weight is 9
node 1 to 5: minimum weight is 7

代码开源在:https://gitee.com/littlebear0729/data-structure-and-algorithm/tree/master/homework3

本文作者 : Littlebear0729
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
本文链接 : https://blog.hailres.xyz/2022/05/%E5%9B%BE%E7%9A%84%E9%81%8D%E5%8E%86%E4%B8%8EDijkstra%E6%9C%80%E7%9F%AD%E8%B7%AF%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0/

本文最后更新于 天前,文中所描述的信息可能已发生改变