Dijkstra算法——通过边实现松弛
- 本算法学习指定一个点(源点)到其余各个顶点的最短路径,也叫做单源最短路径例如求下图1号顶点到2,3,4,5,6号顶点的最短路径
- 这个时候你可能就要问了,为什么不可以直接用上一篇 只有5行的算法:Floyd-Warshall 的方法把所有的最短路都求出来,然后取一行就行了呢?
- Floyd-Warshall算法的时间复杂度是
O(N^3)
,而本文要介绍的Dijkstra算法时间复杂度是O(N^2),而且会在后续的堆里介绍优化本算法的方式。当数据过大时,Floyd-Warshall就不能再规定时间内完成了。
- 与Floyd-Warshall算法一样,边的存储方式是二维数组。
- 这里还需要一个dis数组,来记录1号顶点到每个顶点的距离(长度为n)、
- 与BFS不同(虽然这个算法和bfs没啥太大联系),这个dis数组无需头指针尾指针。
- 当然,book数组是不可缺少的。(这就导致了空间复杂度翻倍)
代码实现
#include<stdio.h>
int a[2000][2000];
int inf = 99999999;
int dis[2000], book[2000];
int main()
{
int i, j, k, m, n, x, y, s, u, v;
int min;
scanf("%d %d", &n, &m);
/* */
//初始化
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i == j)
a[i][j] = 0;
else
a[i][j] = inf;
//读入边(有向图)
for (i = 1; i <= m; i++)
{
scanf("%d %d %d", &x, &y, &s);
a[x][y] = s;
}
for (i = 1; i <= n; i++)
dis[i] = a[1][i];
for (i = 1; i <= n; i++)
book[i] = 0;
book[1] = 1;
//Dijkstra 算法核心语句
for (i = 1; i <= n; i++)
{
//找到离1号顶点最近的点
min = inf;
for (j = 1; j <= n; j++)
{
if (book[j] == 0 && dis[j] < min)
{
min = dis[j];
u = j;
}
}
book[u] = 1;
for (v = 1; v <= n; v++)
{
if (a[u][v] < inf)
{
if (dis[v] > dis[u] + a[u][v])
{
dis[v] = dis[u] + a[u][v];
}
}
}
}
for (i = 1; i <= n; i++)
{
printf("%d ", dis[i]);
}
return 0;
}
运行结果: