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中，用记事本打开可以看到结果。这样方便调试。