Dijkstra算法的C语言实现

Dijkstra算法可用于计算正权图的单源最短路(Single-Source Shortest Paths,SSSP),即从单个源点出发,到所有节点的最短路。该算法同时适用于有向图和无向图。

思想:设置顶点集合S,首先将源点加入集合,然后依据源点到其他顶点的路径的长度,选择路径长度最小的边加入集合,根据所加入的顶点更新源点到其他顶点的路径长度,然后再选取长度最小的边的顶点,依次来做,直到所有的顶点路径都加入集合,也就是求解出了到达所有顶点的路径长度。

算法(文字版):

清除所有点的标号

1
2
3
4
5
6
7
设d[0]=0,其他d[i]=INF(INF是一个很大的数,用以表示不存在的路径)
循环n次
{
在所有未标号的结点中,选出d值最小的结点x
给结点x标记
对于从x出发的所有边(x, y),更新d[y] = min{d[y], d[x] + w[x][y]}
}

完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <string.h>
#define INF 10000
/*INF表示不存在边的长度,用一个很大的数表示它*/
void dijkstra(int w[][21], int [], int n);
int main(void)
{
int n, i, j;
int w[21][21], d[21];
//freopen("dijkstra.in", "r", stdin); //打开文件
//freopen("dijkstra.out", "w", stdout);
scanf("%d", &n); //读入n
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
scanf("%d", &w[i][j]); //读入数据,不存在的边是0
if(w[i][j] == 0) w[i][j] = INF; //把不存在的边0,改成一个很大的数字
}
dijkstra(w, d, n); //调用算法函数
for(i = 0; i < n; i++) //打印结果
printf("%d ", d[i]);
return 0;
}
void dijkstra(int w[][21], int d[], int n)
{
int v[21];
int i, y, x, m;
memset(v, 0, sizeof(v)); //v作为是否访问的标志,0表示没有访问,1表示已经访问
for(i = 0; i < n; i++) d[i] = (i == 0 ? 0 : INF);
for(i = 0; i < n; i++)
{
m = INF;
for(y = 0; y < n; y++) if(!v[y] && d[y] <= m) m = d[x = y];
v[x] = 1;
for(y = 0; y < n; y++) if(d[y] > d[x] + w[x][y]) d[y] = d[x] + w[x][y];
}
}

输入样例:

1
2
3
4
5
6
5
0 4 29 4 0
2 0 0 0 3
0 6 0 0 4
0 0 0 0 6
0 0 4 0 0

输出样例:

1
0 4 11 4 7

大家可以新建dijkstra.txt把输入样例写进去,改名成dijkstra.in,然后解除注释这两行:

1
2
freopen("dijkstra.in", "r", stdin); //打开文件
freopen("dijkstra.out", "w", stdout);

输出在dijkstra.out中,用记事本打开可以看到结果。这样方便调试。

坚持原创技术分享,您的支持将鼓励我继续创作!