2014年11月

   任意两点最短路径被称为多源最短路径,即给定任意两个点,一个出发点,一个到达点,求这两个点的之间的最短路径,就是任意两点最短路径问题,多源最短路径,而Floyd-Warshall算法最简单,只有5行代码,即可解决这个问题。

    比如三个城市,城市1,城市2,城市3。从城市1到城市3需要10公里,从城市1到城市2需要3公里,从城市2到城市3需要4公里,如下图:

4F966EED-1AD1-4FD9-ABB4-0448137A13E4.png


那么从城市1到城市3,如何走更近?1到3是直达,但是却10公里,而1到2到3,虽然转一下,但是距离短了,只要7公里。

这就引出了我们的观念,一个点到另一个点要变短,就要引入第三个点,甚至第四个点,第五个点。


假设在map数组里存储了点i到点j的距离map[i][j],那么我们引入第三个点k,则如果点i到点j的距离比点i到点k加点k到点j,则点i到点j的最短距离是点i到点k加点k到点j。

即如果map[i][j]<map[i][k]+map[k][j],则map[i][j]=map[i][k]+map[k][j]


这就是Floyd-Warshall算法。核心代码如下:

//只能从k中转

    for(k=1; k<=cityCount; k++){

        //从i出发

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

            //到j结束

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

                if(map[i][j] > (map[i][k] + map[k][j])){

                    map[i][j] = map[i][k]+ map[k][j];

                }

            }

        }

    }

三个for循环,加一个if,加一个赋值,简简单单的五行代码,就实现了任意一个点到任意另一个点的最短距离。

显而易见,时间复杂度是O(n3).


完整代码如下

#include <stdio.h>

int map[11][11] = {{0}};

int book[11] = {0};

int main(){

    int i, j, k, cityCount, roadCount, length, x, y;

    scanf("%d %d", &cityCount, &roadCount);

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

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

            map[i][j] = 0;

        }

    }

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

        scanf("%d %d %d", &x, &y, &length);

        map[x][y] = length;

    }

   //只能从k中转

    for(k=1; k<=cityCount; k++){

        //i出发

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

            //j结束

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

                if(map[i][j] == 0 || map[i][k] == 0 || map[k][j] == 0) continue;

                if(map[i][j] > (map[i][k] + map[k][j])){

                    map[i][j] = map[i][k]+ map[k][j];

                }

            }

        }

    }

   //现在的map里就是从一个点i到另一个点j的最短距离map[i][j]

    printf("点1到点5的最短路径是:%d", map[1][5]);

}


输入

5 8

1 2 3

1 3 2

1 5 10

2 3 1

3 5 3

3 4 5

4 5 1

2 4 8


输入,5

图的遍历,我们用深度优先搜索遍历图和广度优先搜索遍历图。最简单的一种图的遍历-穷举!

如下的图:

F1062065-133F-4EB8-AD78-3E7168FF00C7.png

点1和点2,3,5有边,点3和点5有边,点2和点4有边。mac画的好累。。没有鼠标。。


输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。

        5 5

        1 2

        1 3

        1 5

        2 4

        3 5


深度优先搜索来遍历图,代码如下:

#include <stdio.h>

int a[101][101];

int book[101];

int m, n, sum=0;

void dfs(int node);

int main(){

    int i, j, x, y;

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

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

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

            a[i][j] = 0;

        }

    }

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

        scanf("%d %d", &x, &y);

        a[x][y] = 1;

        a[y][x] = 1;

    }

    book[1] = 1;

    dfs(1);

}

void dfs(int node){

    printf("%d ", node);

    sum++;

    if(sum == n){

        return;

    }

    int i = 0;

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

        if(book[i] != 0 || a[node][i] != 1) continue;

        book[i] = 1;

        dfs(i);

    }

}

输出:1,2,4,3,5



广度优先搜索来遍历图,代码如下:

输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。


#include <stdio.h>

int a[101][101];

int book[101];

int m, n;

void dfs(int node);


int main(){

    int i, j, x, y;

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

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

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

            a[i][j] = 0;

        }

    }

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

        scanf("%d %d", &x, &y);

        a[x][y] = 1;

        a[y][x] = 1;

    }

    book[1] = 1;

   //广度优先搜索

    int head = 0, tail = 0;

    int queue[25];

    for(i=0; i<25; i++) queue[i] = 0;

    queue[tail] = 1;

    tail++;

    while(head<tail){

        printf("%d ", queue[head]);

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

            if(book[i] != 0 || a[queue[head]][i] != 1) continue;

            book[i] = 1;

            queue[tail] = i;

            tail++;

        }

        head++;

    }

}

输出:1,2,3,5,4

    上一章我们编写了一个小游戏:炸弹人游戏。使用广度优先搜索解决的,本章将用深度优先搜索来解决。

关于广度优先搜索解决炸弹人游戏和炸弹人游戏的描述》点击查看

什么是深度优先搜索》点击查看    


深度优先搜索的核心代码如下:说白了,就是一条路走到黑,然后回头倒着走看看有没有别的岔路口,不断递归。

void dfs(int x, int y){

    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    int k, sum, tx, ty;

    sum = getnum(x, y);

    if(sum > max){

        max = sum;

        mx = x;

        my = y;

    }

    for(k=0; k<4; k++){

        tx = x + next[k][0];

        ty = y + next[k][1];

        //判断边界

        if(tx<0 || tx > n-1 || ty < 0 || ty > n-1) continue;

        //判断墙和是否走过

        if(a[tx][ty] != '.' || book[tx][ty] != 0) continue;

        book[tx][ty] = 1;

        dfs(tx, ty);

    }

    return;

}


深度优先搜索实现炸弹人游戏的完整代码如下:

#include<stdio.h>

char a[20][20];

int book[20][20], max, mx, my, n, m;

//获取点(i, j)可以炸死多少敌人。

int getnum(int i, int j);

//深度优先搜索,对点(x, y)进行深度优先搜索

void dfs(int x, int y);

void main(){

    int i, startx, starty;

    //地图长n,宽m,起始位置坐标为startx,starty

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

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

        printf("Line : %d", i);

        scanf("%s", a[i]);

    }

    book[startx][starty] = 1;

    max = getnum(startx, starty);

    mx = startx;

    my = starty;

    dfs(startx, starty);

    printf("炸弹放在%d,%d的位置,可以炸死%d人", mx, my, max);

}


int getnum(int i, int j){

    int x, y, sum=0;

    //统计点(i, j)的左边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x--;

    }

    //统计点(i, j)的右边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x++;

    }

    //统计点(i, j)的上边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y--;

    }

    //统计点(i, j)的下边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y++;

    }

    return sum;

}

void dfs(int x, int y){

    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    int k, sum, tx, ty;

    sum = getnum(x, y);

    if(sum > max){

        max = sum;

        mx = x;

        my = y;

    }

    for(k=0; k<4; k++){

        tx = x + next[k][0];

        ty = y + next[k][1];

        //判断边界

        if(tx<0 || tx > n-1 || ty < 0 || ty > n-1) continue;

        //判断墙和是否走过

        if(a[tx][ty] != '.' || book[tx][ty] != 0) continue;

        book[tx][ty] = 1;

        dfs(tx, ty);

    }

    return;

}


输入:第一次要求输入地图的长、宽、起始X坐标、起始Y坐标:13 13 3 3


第二次要求输入的就是地图了,每次一行,如下:

#############

#GG.GGG#GGG.#

###.#G#G#G#G#

#.......#..G#

#G#.###.#G#G#

#GG.GGG.#.GG#

#G#.#G#.#.#.#

##G...G.....#

#G#.#G###.#G#

#...G#GGG.GG#

#G#.#G#G#.#G#

#GG.GGG#G.GG#

#############


输出:炸弹放在7,11的位置,可以炸死10人.


Ps:代码案例来源于《啊哈!算法》一书

    什么是广度优先搜索?广度优先搜索也称为宽度优先搜索,一层一层不断的扩展来达到搜索的目的。以一个点为中心,将上下左右4个点都搜索过后,再以这4个点分别为中心点,搜索该中心点的上下左右4个点,依次类推。

    场景:比如我们要从点(1,1)到点(5,5),我们使用广度优先算法来找出最短路劲。

    第一步:将点(1,1)的上下左右4个点找出,走过的点忽略,不能走的点忽略(比如水,墙),那么只有(1,2)和(2,1)2个点,因为(1,0)和(0,1)已经超出了地图范围。

    第二步:将第一步得出的点(1,2)的上下左右4个点找出,走过的点忽略,不能走的点忽略,那么只有(1,3)和(2,2)2个点,因为(0,2)已经超出了地图范围,(1,1)已经走过了。

    第三步:将第一步得出的将点(2,1)的上下左右4个点找出,走过的点忽略,不能走的点忽略,那么只有(3,1)这一个点,因为(2,0)已经超出了地图范围,(1,1)已经走过了。(2,2)在第二部已经得出了。

    ……

    依次类推,将每个点都尝试过后,则比较每种方式的长度,得出最短路径。


    代码将展示另一个实例。我们都玩过炸弹人的游戏,地图中有墙和敌人,在地图的空地上方一个炸弹,炸弹会在上下左右4个直线方向炸出4道火花,敌人会被炸死,而墙不会受到影响。基于此,我们用广度优先算法来实现哪个点可以炸死的敌人数量最多。


    1、建立一个队列,将起点(人物刚出的时候在地图的位置)作为队列的第一个元素。按照队列的顺序来执行。

    2、将这个点的上下左右4个点也依次入队。然后把起点出队。

    3、这时把队列的第一个元素(起点的右边的点)作为中心点,将这个点的上下左右4个点依次入队,然后这个点出队。            4、这时把队列的第一个元素(起点的下边的点)作为中心点,将这个点的上下左右4个点依次入队,然后这个点出队。            5、这时把队列的第一个元素(起点的左边的点)作为中心点,将这个点的上下左右4个点依次入队,然后这个点出队。            6、这时把队列的第一个元素(起点的上边的点)作为中心点,将这个点的上下左右4个点依次入队,然后这个点出队。            7、这时把队列的第一个元素(起点的右边的点的右边的点)作为中心点,将这个点的上下左右4个点依次入队,然后这个点出队。

    ……

    依次类推,总之,就是把一个点作为中心点,然后把这个点的上下左右依次入队,按照队列顺序,队列中每个点都要作为中心点,把中心点上下左右4个点依次入队。直到队列没有元素时停止。

    我们约定,敌人为“G”,墙为“#”,空地为“.”。

    计算一个点可以炸死的敌人数量的函数getnum()如下:

int getnum(int i, int j){

    int x, y, sum=0;

    //统计点(i, j)的左边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x--;

    }

    //统计点(i, j)的右边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x++;

    }

    //统计点(i, j)的上边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y--;

    }

    //统计点(i, j)的下边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y++;

    }

    return sum;

}


    入队操作的代码如下:

//起点入队

    que[tail].x = startx;

    que[tail].y = starty;

    tail++;

    book[startx][starty] = 1;

    max = getnum(startx, starty);

    mx = startx;

    my = starty;


    广度优先搜索的核心代码如下:

//广度优先搜索的核心部分

    while(head < tail){

        for(k = 0; k< 4; k++){

            tx = que[head].x + next[k][0];

            ty = que[head].y + next[k][1];

            //越界

            if(tx<0 || tx>n-1 || ty<0 || ty>n-1) continue;

            //不是平地?以前走过了?

            if(a[tx][ty]!='.' || book[tx][ty]!=0) continue;

            //这个点可以走,并且没走过,就标记为走过了,然后入队

            book[tx][ty] = 1;

            que[tail].x = tx;

            que[tail].y = ty;

            tail++;

            sum = getnum(tx, ty);

            if(sum > max){

                max = sum;

                mx = tx;

                my = ty;

            }

        }

        //这个点的上下左右都看过了,就出队

        head++;

    }


    完整的代码如下:

#include<stdio.h>

struct Note{

    int x;

    int y;

};

char a[20][20];

//获取点(i, j)可以炸死多少敌人。

int getnum(int i, int j);

void main(){

    struct Note que[401];

    int head=1, tail=1;

    int book[20][20] = {0};

    int i, k, tx, ty, startx, starty, sum, max=0, mx, my, m, n;

    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    //地图长n,宽m,起始位置坐标为startx,starty

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

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

        printf("Line : %d", i);

        scanf("%s", a[i]);

    }

    //起点入队

    que[tail].x = startx;

    que[tail].y = starty;

    tail++;

    book[startx][starty] = 1;

    max = getnum(startx, starty);

    mx = startx;

    my = starty;

    //广度优先搜索的核心部分

    while(head < tail){

        for(k = 0; k< 4; k++){

            tx = que[head].x + next[k][0];

            ty = que[head].y + next[k][1];

            //越界

            if(tx<0 || tx>n-1 || ty<0 || ty>n-1) continue;

            //不是平地?以前走过了?

            if(a[tx][ty]!='.' || book[tx][ty]!=0) continue;

            //这个点可以走,并且没走过,就标记为走过了,然后入队

            book[tx][ty] = 1;

            que[tail].x = tx;

            que[tail].y = ty;

            tail++;

            sum = getnum(tx, ty);

            if(sum > max){

                max = sum;

                mx = tx;

                my = ty;

            }

        }

        //这个点的上下左右都看过了,就出队

        head++;

    }

    printf("炸弹放在%d,%d的位置,可以炸死%d人", mx, my, max);

}


int getnum(int i, int j){

    int x, y, sum=0;

    //统计点(i, j)的左边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x--;

    }

    //统计点(i, j)的右边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x++;

    }

    //统计点(i, j)的上边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y--;

    }

    //统计点(i, j)的下边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y++;

    }

    return sum;

}


输入:第一次要求输入地图的长、宽、起始X坐标、起始Y坐标:13 13 3 3

第二次要求输入的就是地图了,每次一行,如下


#############

#GG.GGG#GGG.#

###.#G#G#G#G#

#.......#..G#

#G#.###.#G#G#

#GG.GGG.#.GG#

#G#.#G#.#.#.#

##G...G.....#

#G#.#G###.#G#

#...G#GGG.GG#

#G#.#G#G#.#G#

#GG.GGG#G.GG#

#############


输出:炸弹放在7,11的位置,可以炸死10人.


Ps:代码案例来源于《啊哈!算法》一书


炸弹人游戏本篇用广度优先搜索来解决,也可以深度优先搜索来实现。关于《深度优先搜索实现炸弹人游戏》点击查看

    什么是深度优先搜索?理解深度优先搜索的关键在于解决“当前如何做”,至于“下一步如何做”和“当前如何做是一样的做法”。深度优先搜索是Depth First Search, DFS。基本模型如下:

void dfs(int step){

    边界判断

    循环遍历去尝试每一种可能for(int i=0; i<n; i++){

        继续下一步dfs(step + 1);

    }

}

    下面看一个实例。我们有三个数字,1,2,3.求这三个数字的所有可能的搭配。那么,答案就是123,132,213,231,312,321共6种。我给出的答案顺序,也是深度优先搜索的顺序。

    假设我们有1,2,3的三张牌,地上有编号为一、二、三的三个纸箱。我们每次都把手中最小的牌放到箱子里,然后走到下一个箱子。

    第一步:在一号箱子面前,放入最小的手牌1,然后前进一步。此时手牌是2和3。判断边界(手牌是否为空)。

    第二步:在二号箱子面前,放入最小的手牌2,然后前进一步。此时手牌是3。判断边界(手牌是否为空)。

    第三步:在三号箱子面前,放入最小的手牌3,然后前进一步,此时手牌是空。判断边界(手牌是否为空)。

    第四步:手牌为空,触发边界条件。遍历打印箱子中的数字,结果是123。

    第五步:取出三号箱子的牌,后退一步。此时手牌是3。

    第六步:取出二号箱子的牌,此时手牌是2和3,2已经放过了,所以放3,然后前进一步。此时手牌是2。判断边界(手牌是否为空)。

    第七步:在三号箱子面前,放入最小手牌2,然后前进一步,此时手牌是空。判断边界(手牌是否为空)。

    第八步:手牌为空,触发边界条件。遍历打印箱子中的数字,结果是132。

    第九步:取出三号箱子的牌,后退一步。此时手牌是2。

    第十步:取出二号箱子的牌,此时手牌是2和3,2和3都已经放过了,所以再退一部。此时手牌是2。判断边界(手牌是否为空)。

    第十一步:取出一号箱子的牌,此时手牌是1,2和3,1以及放过了,所以放剩下的最小手牌,就是2,然后前进一步,此时手牌是1,3。判断边界(手牌是否为空)。

    第十二步:在二号箱子面前,放入最小的手牌1,然后前进一步。此时手牌是3。判断边界(手牌是否为空)。

    第十三步:在三号箱子面前,放入最小的手牌3,然后前进一步,此时手牌是空。判断边界(手牌是否为空)。

    第十四步:手牌为空,触发边界条件。遍历打印箱子中的数字,结果是213。

    ………………………………………………………………………………

    恩,就是这样子,直接上代码了。C版本的深度优先遍历的模型。

    Ps:本实例和代码均来自《啊哈!算法》一书。不过上面的过程是我自己手打原创哦^_^

#include <stdio.h>

void dfs(int step);

int a[10], book[10], n;

int main(){

    //1-9的整数

    scanf("%d", &n);

    //从第一个箱子开始。直接从下标1开始。0不要了。

    dfs(1);

}

void dfs(int step){

    int i;

    //已经到最后一个箱子了。

    if(step == n+1){

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

            printf("%d", a[i]);

        }

        printf("\n");

    }

    //在第step个箱子面前,按照1,2,3...n的顺序一一尝试

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

        //等于0就是i还没有使用,还在手里。

        if(book[i] == 0){

            //使用i

            a[step] = i;

            //标记i已经使用

            book[i] = 1;

            //前进一步

            dfs(step + 1);

            //回收step箱子里的牌

            book[i] = 0;

        }

    }

}