# Dijkstra 算法
# 简介
迪杰斯特拉算法 (Dijkstra) 是由荷兰计算机科学家狄克斯特拉于 1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
Dijkstra 算法可用来求一个图中一个点到其他所有点的最短路径，时间复杂度为 O (n2)，可优化为 O (nlogn)。
# 案例
如图，求源点 V1 到其它几个点的最短距离。
# 要点
int map[n+5][n+5] // 采用邻接链表的方式记录图信息 | |
int dis[n] // 用于存储源点到其它 n-1 个点的最短距离 | |
bool v[n] // 用于记录每个点的搜索状态，false 表示未搜 |
从源点出发，每次找出 dis 中离源点最近的且未走过的点，替换出发点，更新 dis 的值。
# 算法详解
首先用邻接矩阵存储图信息，如下：
{ | |
{ 0, 8, 2, ∞, ∞, 5, ∞ }, | |
{ 8, 0, ∞, 2, ∞, ∞, ∞ }, | |
{ 2, ∞, 0, 3, ∞, ∞, 4 }, | |
{ ∞, 2, 3, 0, 4, ∞, ∞ }, | |
{ ∞, ∞, ∞, 4, 0, ∞, 2 }, | |
{ 5, ∞, ∞, ∞, ∞, 0, 2 }, | |
{ ∞, ∞, 4, ∞, 2, 2, 0 } | |
} |
接着初始化 dis 数组，此时 dis[0, 8, 2, ∞, ∞, 5, ∞]
一开始 start = 1 ，令 v[1] = 1 表示 V1 点已搜；接着遍历 dis 数组，找出当前距离源点最近且未搜的点，这里为 V3 (距离为 2)，令 start = 3 ， v[3] = 1 ；然后更新 dis 数组 (当 dis[start] + map[start][i] < dis[i] 时，更新 dis[i] 的值)，为 dis[0, 8, 2, 5, ∞, 5, 6] 。
重复上述步骤，依次如下：
start = 4 ，更新为 dis[0, 7, 2, 5, 9, 5, 6]start = 6 ，更新为 dis[0, 7, 2, 5, 9, 5, 6]start = 7 ，更新为 dis[0, 7, 2, 5, 8, 5, 6]start = 2 ，更新为 dis[0, 7, 2, 5, 8, 5, 6]start = 5 ，更新为 dis[0, 7, 2, 5, 8, 5, 6]
直到所有点都搜索过，此时 dis 数组即为源点 V1 到各个点的最短距离。
# 完整代码
#include <iostream> | |
#include <cstring> | |
using namespace std; | |
//n 表示点的个数，m 表示边的个数，s 表示源点编号，这题为 1，mins 用于找出最小值 | |
int n, m, s, mins; | |
int mp[10001][10001], dis[10001]; | |
bool v[10001]; | |
int main() | |
{ | |
cin >> n >> m >> s; | |
int a, b, c; | |
memset(mp, 127, sizeof(mp)); | |
for(int i = 0; i < m; i ++){ | |
cin >> a >> b >> c; // 表示 a 到 b 有一条权值为 c 的边 | |
mp[a][b] = mp[b][a] = c; // 无向边 | |
} | |
int t; // 记录当前未搜最近点 | |
for(int i = 1; i <= n; i ++) dis[i] = mp[s][i]; // 初始化 dis | |
v[s] = 1; // 记录初始点已走 | |
dis[s] = 0; // 初始化，源点到源点自然是 0 | |
for(int k = 1; k <= n; k ++){ | |
mins = 0x7fffffff; // 令 mins 为极大值 | |
for(int i = 1; i <= n; i ++){ // 遍历找出当前距离源点最近且未搜的点 | |
if(!v[i] && dis[i] < mins){ | |
mins = dis[i]; | |
t = i; // 用 t 记下来 | |
} | |
} | |
v[t] = 1; // 记录 t 点搜索状态 | |
for(int i = 1; i <= n; i ++){ // 更新 dis | |
if(mp[t][i] && !v[i] && dis[t]+mp[t][i] < dis[i]) | |
dis[i] = dis[t] + mp[t][i]; | |
} | |
} | |
// 输出最终结果 | |
for(int i = 1; i <= n; i ++) cout << dis[i] << " "; | |
return 0; | |
} |
# 案例测试
输入数据
7 9 1 | |
1 2 8 | |
1 3 2 | |
1 6 5 | |
2 4 2 | |
3 4 3 | |
3 7 4 | |
6 7 2 | |
4 5 4 | |
5 7 2 |
输出结果
0 7 2 5 8 5 6 |
