LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

算法十一:Dijkstra算法 - 一个点到各个点的最短路径

Clicks: 8586 Date: 2014-12-23 22:49:28 Power By 李轩Lane

    

    Dijkstra算法是指定一个源点,求得这个源点到各个点的最短路径。Dijkstra算法通过不断的松弛边,每次更新相邻点的路径,使之两点之间的距离成为最短的路径。Dijkstra算法缺点是不能有负权边的值。

    松弛边:点A到点B的距离是10,点A到点C的距离是15,点B到点C的距离是3,那么点A到点C的最短距离就是13。此时15这个值将会被废弃,永不使用,以后谈论点A到点C的距离都是直接说13。这就是松弛边。

    现在有如下图,6个点,9条边,边是有方向的哦。


无标题.jpg


    Dijkstra算法的步骤,假设源点为点(1):

    1、先求得源点到各个点的距离。则数组为dis['1'=>0, '2'=>1, '3'=>12, '4'=>'∞', '5'=>'∞', '6'=>'∞'];并且用数组e[i][j]表示点i到点j的距离。

    2、将各个点分为2个部分,P部分是已知的点1到该点距离为最短路径的点的集合,此时P部分只有点1到点1的距离为0是已知的,点1到点2,点1到点3的距离是不是最短路径暂时不可是,所以他们不属于这部分。Q部分是未知的点1到该点距离为最短路径的点的集合。

    3、在集合Q中选择一个点,这个点距离源点(1)号点最近,即步骤一得出的dis数组中该key所对应的值最小,此时这个点为2号点,因为dis[2]最小,为1。则点1到点2的距离dis[2]是最短的路径,已经已知了,所以将(2)号点加入到集合P中。此时以(2)好点为源点,对所有的边松弛一次,看看有没有一个点X,可以使得点1到点2再到点X的距离小于点1到点X的距离,如果有,则点1到点X的最短路径就是点1到点2再到点X的值。即如果dis[3] > dis[2] + e[2][x],则dis[3] = dis[2] + e[2][x]。

    4、重复第三步,知道集合Q为空。


Dijkstra算法的代码如下:

#include <stdio.h>

int main(){

    int startPoint = 1;

    int limitValue = 999;

    int e[10][10], dis[10], book[10], i, j, m, n, point1, point2, length, u, v, min;

    //n是点数,m是边数

    scanf("%d %d", &n, &m);

    //如果i=j,就是自己到自己的距离,那么就是0,否则,就初始化非正无穷

    for(i=1; i<=n; i++){

        for(j=1; j<=n; j++){

            if(i==j)

                e[i][j] = 0;

            else

                e[i][j] = limitValue;

        }

    }

    //边的长度,即点到点的距离

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &point1, &point2, &length);

        e[point1][point2] = length;

    }

    //初始化源点到各点的距离的数组, 我们的源点为1

    for(i=1; i<=n; i++){

        dis[i] = e[startPoint][i];

    }

    //book数组用来标记那个点是已经走过了的。

    for(i=1; i<=n; i++){

        book[i] = 0;

    }

    //从源点开始

    book[startPoint] = 1;

    //以下就是Dijkstra算法的重点,是核心思想

    for(i=1; i<=n-1; i++){

        //找到离远点最近的点

        min = limitValue;

        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++){

            //如果小于limitValue,则证明点u到点v是有路走的

            if(e[u][v] < limitValue){

                if(dis[v] > dis[u] + e[u][v]){

                    dis[v] = dis[u] + e[u][v];

                }

            }

        }

    }

    //输出

    for(i=0; i<=n; i++){

        printf("%d ", 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

这个输出便是点1到各个点的最短距离。


Ps:本算法参考《啊哈!算法》一书。

©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号