算法 Dijkstra 单源最短路

/*
Dijkstra 算法思想:每次找到离源点s最近的一个顶点u（那么dis[u] 就是源点到顶点u的最短距离，因为
u是离源点s最近的点dis[v]>dis[u]，不可能出现 dis[u]>dis[v]+e[v][u]），然后以该顶点u为中心进行扩展，通过判断dis[v]和
dis[u]+e[u][v] 的大小，来对边进行松弛（其实就是消除顶点u对dis[v]的影响），然后将顶点u做个标记，继续
在其余顶点中，找离源点最近的顶点，重复上述操作_{，直到每个顶点都标记啦}

基本步骤如下：
1.将所有的顶点分为两个部分：已知最短路程的顶点集合P和未知最短路程的顶点集合Q，最开始，已知最短路径的顶点
集合P只有源点一个顶点。我们这里用book数组来记录哪些点在集合P中，book[i]=1;表示顶点i在集合P中
2.设置源点s到自己的最短路径为0，即dis[s] =0;若存在源点s能直接到达的顶点i，则dis[i]设置为e[s][i]。同
时把其他不能直接到达的顶点的最短距离设置为∞
3.在集合Q中的所有顶点中选择一个离源点s最近的顶点u(即dis[u]最小),加入到集合P中(book[u]=1)。并考察所
有以点u为起点的边，对每一条边做松弛操作。例如存在一条从u到v的边，那么通过这条边可以扩展一条从s到v的路
径，这条路径的长度为dis[u]+e[u][v],如果这个值比已知的dis[v]小，则更新dis[v];
4.重复第3步操作。如果集合Q为空，算法结束。最终dis数组中的值就是源点s到所有顶点的最短路径

Dijkstra 算法

源点1到各个顶点的最短距离？

屏幕快照 2018-04-26 下午6.05.27.png


-(void)test1 {
    /*
     e[i][j] 表示i到j的距离
     如果i==j，则e[i][j]=0;
     如果i无法到达j 则 e[i][j] = 9999;(代表无穷大)
     */
    
    int e[10][10];
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            if (i==j) {
                e[i][j] =0;
            }else {
                e[i][j] =9999;
            }
        }
    }
    
    e[1][2] =1;
    e[1][3] =12;
    e[2][3] =9;
    e[2][4] =3;
    e[3][5] =5;
    e[4][3] =4;
    e[4][5] =13;
    e[4][6] =15;
    e[5][6] =4;
    
    int n=6; // 共有6个顶点
    int book[10]={0};
    int dis[10]; //  记录原点s到其他各点的距离
    for (int i=0; i<10; i++) {
        dis[i] = e[1][I];
    }

    int u=1; // 记录当前离源点最近的点
    int min;
    book[1] =1;
    
    
    for (int j=1; j<=n; j++) {
        // 找到离源点1最近的顶点
        min = 9999;
        for (int i=1; i<=n; i++) {
            if (book[i]==0 && dis[i]<min) {
                min =dis[I];
                u =I;
            }
        }
        
        // 标记
        book[u]=1;
        // 松弛顶点u的边 即 通过顶点u，计算所有源点1 到其他各点的最小距离
        // dis[u] 表示源点到u的最短距离
        for (int v=1; v<=n; v++) {
            if (dis[v]>dis[u] + e[u][v]) {
                dis[v] = dis[u] + e[u][v];
            }
        }
    }
    
    
    // 打印 源点1到各个顶点的最短距离
    for (int i=1; i<=n; i++) {
        printf("顶点1到顶点%d的最短距离%d",i,dis[I]);
        printf("\n");
    }
    
    
}

源点1到其他各顶点的最短距离？

屏幕快照 2018-04-26 下午4.11.23.png

-(void)test2 {
    int e[10][10];
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            if (i==j) {
                e[i][j]=0;
            }else{
                e[i][j]=999;
            }
        }
    }
    e[1][2]=2;
    e[1][3]=6;
    e[1][4]=4;
    e[2][3]=3;
    e[3][1]=7;
    e[3][4]=1;
    e[4][1]=5;
    e[4][3]=12;
    
    int dis[10];
    for (int i=0; i<10; i++) {
        dis[i] = e[1][I];
    }
    
    int book[10] ={0};
    int n=4; //顶点数
    
    int u = 0;
    int min;
    
    // 源点标记为1
    book[1]=1;
    
    for (int j=1; j<=n; j++) {
        
        min =9999;
        // 找离源点1最近的点
        for (int i=1; i<=n; i++) {
            if (book[i]==0 && dis[i]<min) {
                min =dis[I];
                u = I;
            }
        }
        
        // 标记u
        book[u]=1;
        // 对u所有的边进行松弛操作
        for (int v=1; v<n; v++) {
            if (dis[v]>dis[u]+e[u][v]) {
                dis[v] = dis[u] + e[u][v];
            }
        }
    }
    
    // 打印 源点1到各个顶点的最短距离
    for (int i=1; i<=n; i++) {
        printf("顶点1到顶点%d的最短距离%d",i,dis[I]);
        printf("\n");
    }
    
}

最后编辑于：2018.04.27 18:39:36