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;elsea[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;
}