0%

dijkstra算法

发表于 更新于 阅读次数：

dijkstra算法

  • 思想与原理就不再此文章赘述，就算讲我也讲不清楚，若不了解建议先去度娘那里了解后，再来食用此文章更佳，本文章就直接说算法实现。

算法步骤

从dijkstra算法思想上可知，找最短路时分了两个集合，一个集合里面的元素表示已经达到最短路径的点，设为集合A，另外一个集合则相反，设为集合B。
算法分为以下步骤：  
1.初始时，集合A为空，集合B包含所有点，并且源点到其它点的距离为无穷，到自己的距离为0。  
2.从集合B中选出离源点最近的点，将该点加入集合A，若B集合为空，则算法结束。
3.用选出来的点来更新剩余点的最短距离，回到第2步。

算法实现

  • 从算法步骤课看出，每次都是用最短距离来更新距离，若没有负权边，则更新后的距离若为集合B中的最小的距离，那么一定会是一个最短距离，证明很简单,这里就口嗨略过了。所以dijkstra算法是无法处理有负权边的图的，只适用于正权图。
  • 对于步骤1，是求最短路时的初始化阶段。因为只有两个集合，那么1位二进制就可以表示两个集合了，所以对于每个点都有一个标记，用于判断属于哪个集合。这里用1表示A集合，0表示B集合
    1
    2
    3
    4
    5
    6
    7
    8
    int flag[maxn]; //标记
    int dis[maxn]; // dis[i] 表示源点到i点的最短距离
    int st; //源点
    void init(){
        memset(flag, 0, sizeof(flag)); //表示初始时，所有点都属于集合B
        memset(dis, 0x3f,sizeof(dis)); //memset初始化技巧，这样初始化的值用16进制表示为3F3F3F3FH，十进制为1061109567，属于int范围内，可用于表示1e9范围内的极大值  
        dis[st] = 0; // st表示源点，源点到源点的距离为0
    }
  • 对于步骤2与3，直接用代码解释。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    int n; // 表示点的数量
    int mp[maxn][maxn];//用邻接矩阵来存图,以后再讲邻接表
    void dijkstra(){
        init();//每次调用初始化
        for(int k=0;k<n;k++){//只循环n次是有目的的，可以自己分析一波
            int pos = -1; 
            // 找出集合B中离源点最近的点
            for(int i=1;i<=n;i++){ // 点的下标从1开始
                if(!flag[i] && (pos == -1||dis[pos] > dis[i])){ // 若有多个满足条件的，任意选一个
                    pos = i;
                }
            }
            if(pos == -1) break; // pos为-1表示算法结束，无法继续更新最短路
            flag[pos] = 1; // 将该点加入集合A
            for(int i=1;i<=n;i++){
                if(flag[i]) continue; // 属于集合A则跳过
                if(dis[i] > dis[pos]+mp[pos][i]) //判断距离是否需要更新
                    dis[i] = dis[pos] + mp[pos][i];
            }
        }
    }

代码实践

  • 求1其它所有点的最短路径，并全部输出出来。该图的边没有方向，没有重边，没有负权边。 
    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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    代码:
    #include <stdio.h>
    #include <string.h>
    const int maxn = 1e3 + 5;
    const int maxm = 1e4 + 5;
    int mp[maxn][maxn];
    int dis[maxn];
    int flag[maxn];
    int n, m, st;
    void init(){
        memset(flag, 0, sizeof(flag)); 
        memset(dis, 0x3f,sizeof(dis)); 
        dis[st] = 0; 
    }
    void dijkstra(){
        init();
        for(int k=0;k<n;k++){
            int pos = 0; 
            for(int i=1;i<=n;i++){
                 if(!flag[i] && (pos == -1||dis[pos] > dis[i])){
                    pos = i;
                }
            }
            if(pos == 0) break; 
            flag[pos] = 1; 
            for(int i=1;i<=n;i++){
                if(flag[i]) continue; 
                if(dis[i] > dis[pos]+mp[pos][i]) 
                    dis[i] = dis[pos] + mp[pos][i];
            }
        }
    }
    int main(){
        scanf("%d %d", &n, &m);
        memset(mp, 0x3f, sizeof(mp));
        for(int i=0;i<m;i++){
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            mp[u][v] = w;
            mp[v][u] = w; // 双向边
        }
        st = 1;
        dijkstra();
        for(int i=2;i<=n;i++){
            printf("1~%d：%d\n", i, dis[i]);
        }
        return 0;
    }
    /*
    测试数据:
    5 6
    1 2 6
    1 4 2
    4 5 1
    5 2 2
    1 3 10
    3 2 3
    */
  • 测试结果
    测试结果