LaneBlog

蝼蚁虽小,也有梦想

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

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

Clicks: 14099 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:本算法参考《啊哈!算法》一书。

Reply: Edyawattal On 2020-03-09 03:37:11

Propecia La Web http://apcialisle.com/# - Cialis Cialis En Angleterre <a href=http://apcialisle.com/#>Buy Cialis</a> Fast Shipping Prednisone

回复

Reply: Edyawattal On 2020-03-21 21:45:32

Clomid Online Overnight https://apcialisle.com/# - buy cialis online without prescription Levitra Generique Maroc <a href=https://apcialisle.com/#>Cialis</a> Valor De Propecia

回复

Reply: jewellOt On 2020-04-01 03:13:47

<a href=https://www.youtube.com/watch?v=gSLQ9Gd5SWM>mute video</a>

回复

Reply: Keytboarm On 2020-04-29 13:15:46

Prescribed Ciprodex Otic And Amoxicillin https://buycialisuss.com/# - Cialis Www Rx Customer Support <a href=https://buycialisuss.com/#>Cialis</a> Retin A What Strength Does Itcome It

回复

Reply: Trista On 2020-05-16 14:05:13

I blog often and I seriously thank you for your information. This great article has really peaked my interest. I'm going to take a note of your blog and keep checking for new information about once a week. I subscribed to your RSS feed as well.

回复

Reply: Kerry On 2020-05-18 01:17:11

Hello there! Quick question that's completely off topic. Do you know how to make your site mobile friendly? My web site looks weird when browsing from my iphone 4. I'm trying to find a theme or plugin that might be able to fix this problem. If you have any suggestions, please share. Appreciate it!

回复

Reply: Mazie On 2020-05-22 01:51:15

Please let me know if you're looking for a article author for your site. You have some really good posts and I feel I would be a good asset. If you ever want to take some of the load off, I'd really like to write some content for your blog in exchange for a link back to mine. Please shoot me an email if interested. Cheers!

回复

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