/*
Dijkstra 算法思想:每次找到離源點s最近的一個頂點u（那么dis[u] 就是源點到頂點u的最短距離，因為
u是離源點s最近的點dis[v]>dis[u]，不可能出現(xiàn) dis[u]>dis[v]+e[v][u]），然后以該頂點u為中心進(jìn)行擴展，通過判斷dis[v]和
dis[u]+e[u][v] 的大小，來對邊進(jìn)行松弛（其實就是消除頂點u對dis[v]的影響），然后將頂點u做個標(biāo)記，繼續(xù)
在其余頂點中，找離源點最近的頂點，重復(fù)上述操作_{，直到每個頂點都標(biāo)記啦}

基本步驟如下：
1.將所有的頂點分為兩個部分：已知最短路程的頂點集合P和未知最短路程的頂點集合Q，最開始，已知最短路徑的頂點
集合P只有源點一個頂點。我們這里用book數(shù)組來記錄哪些點在集合P中，book[i]=1;表示頂點i在集合P中
2.設(shè)置源點s到自己的最短路徑為0，即dis[s] =0;若存在源點s能直接到達(dá)的頂點i，則dis[i]設(shè)置為e[s][i]。同
時把其他不能直接到達(dá)的頂點的最短距離設(shè)置為∞
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.重復(fù)第3步操作。如果集合Q為空，算法結(jié)束。最終dis數(shù)組中的值就是源點s到所有頂點的最短路徑

*/

Dijkstra 算法

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

-(void)test1 {
    /*
     e[i][j] 表示i到j(luò)的距離
     如果i==j，則e[i][j]=0;
     如果i無法到達(dá)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; // 記錄當(dāng)前離源點最近的點
    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;
            }
        }
        
        // 標(biāo)記
        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");
    }
    
    
}

屏幕快照 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; //頂點數(shù)
    
    int u = 0;
    int min;
    
    // 源點標(biāo)記為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;
            }
        }
        
        // 標(biāo)記u
        book[u]=1;
        // 對u所有的邊進(jìn)行松弛操作
        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");
    }
    
}