Dijkstra算法(最短距离)

该算法由荷兰的一个牛人计算机科学家Edsger Wybe Dijkstra在1956年发现。

 

这套算法主要解决计算从一个点到其它的点的最短距离，而不是Floyd-Warshall算法的任意两点距离。

 如图，现要计算出，从1号点到其它各点的最短距离，首先我还是转化成矩阵

由此可见1号点到其它点的初始距离为：

 

0 1 12 ∞ ∞ ∞

 

 很明显2号点是离1号点最近的点，那么1号点到2号点的最短距离肯定就是直达了。那我就将2号点作为“换乘点”，来计算下距离：

 

0 1 10 4 ∞ ∞

 

 这个过程有个专业术语“松弛”。2号点我也已经用了，那么4号点是离1号最近的点了，那再用它来松弛下：

 

0 1 8 4 17 19

 接下来，就不费话了，继续松弛吧，直到所有点都用来松过。

 

这就是Dijkstra算法的思想，略屌，略屌！

现在用C来实现下：

 

#include <stdio.h>

int main()
{
    int a[10][10], dis[10], book[10], n, m, t1, t2, t3, i, j, k, min, u;

    int inf = 99999999;//这里定义的正无穷

    //读入nm,n为顶点数，m为边的条数
    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", &t1, &t2, &t3);
        a[t1][t2] = t3;
    }

    //初始化dis，这里存的是从1号顶点到其它顶点的初始距离
    for(i = 1; i <= n; i++)
        dis[i] = a[1][i];


    //初始化book，标记某个点是否已经“松弛”过了
    for(i = 1; i <= n; i++)
        book[i] = 0;
    book[1] = 1;//从1到1的距离是0，为确定距离

    //Dijkstra算法核心代码
    for(i = 2; i <= n; i++)//这里从2开始，因为1号到1号不用算了。下面也一样
    {
        min = inf;
        //找到离i最近的顶点
        for(j = 2; j <= n; j++)
        {
            if(book[j] == 0 && dis[j] < min)
            {
                min = dis[j];
                u = j;
            }
        }
        book[u] = 1;

        for(k = 1; k <= n; k++)
        {
            if(a[u][k] < inf && dis[k] > dis[u] + a[u][k])
            {
                dis[k] = dis[u] + a[u][k];
            }
        }
    }

    for(i = 1; i <= n; i++)
        printf("%d \n", dis[i]);

    return 0;
}

 输入：

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4

 得到结果：

0 1 8 4 13 17

 这套程序的时间复杂度为O(N2)。想想有什么办法还能优化它。