【Floyd - Warshall 弗洛伊德算法+看了3篇总结出的思路】案例6-1.6 哈利·波特的考试

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
文章字体风格：
红色文字表示：重难点
蓝色文字表示：思路以及想法

算法解析

上一篇，我们已经学过了【Dijkstra迪杰斯特拉算法+苦学两天所总结的逻辑】案例6-1.5 旅游规划
迪杰斯特拉算法，算得是一个图中，所有节点到一个头结点或者指定节点，的最短距离。接下来，我们要算，一个图中，所有点之间，每两点之间的最短距离，我们所应用的算法就是（弗洛伊德算法）

算法思路：

1. 首先我们需要一个二维数组存储图。注意没有之间相连接的点，都要赋值为无限大
2. 既然我们要找到所有点之间的最短距离，那么就需要创建一个二维数组，来存储最短距离。注意先存储的是之间相连接的图，并且未连接的点，距离都是无限大。
3. 弗洛伊德算法的思想就是，构建一个循环，遍历每个节点，每次遍历的时候，把这个节点确定，然后再遍历所有节点队，判断两两的节点队，是否可以通过当前节点，从而达到缩短路径的效果，如果可以，那么更新最短路径即可，这就是弗洛伊德算法
4. 关键是如何判断，两个点A,B是否可以通过一个节点C，从而达到缩短路径呢？我们可以通过判断两个点的直接距离，是否比两个点分别到C的距离之和 小，如果小，说明两个点可以通过C缩短距离。
5. 这就是伟人的算法思想，我们先学习过程，至于伟人是怎么想到的，我们暂且可以不考虑，所以直接通过过程背诵模板即可，牢记是通过 过程背诵！！！

for(int k = 1 ; k <= n ; k ++)
{
        for(int i = 1 ; i <= n ; i ++)
        {
                for(int j = 1 ; j <= n ; j ++)
                {
                        if(e[i][j] > e[i][k] + e[k][j])
                                e[i][j] = e[i][k] + e[k][j];
                 }
        }
}
1
2
3
4
5
6
7
8
9
10
11

例题

案例6-1.6 哈利·波特的考试

#include
#define INT 0x3f3f3f3f
using namespace std;
int main()
{
    int a,b,c[110][110],e,f,g,h,i,j,k,min=INT,max,n;
    for(e=0;e<110;e++)//设初值
        for(f=0;f<110;f++)
        {
            if(e==f)//初值自己变自己就是零喽
                c[e][f]=0;
            else
                c[e][f]=INT;
        }
    cin>>a>>b;
    while(b--)
    {
        cin>>e>>f>>g;
        c[e][f]=c[f][e]=g;
    }
    for(k=1;k<=a;k++)//floyd算法
        for(i=1;i<=a;i++)
            for(j=1;j<=a;j++)
            {
                if(c[i][j]>c[i][k]+c[k][j])
                    c[i][j]=c[i][k]+c[k][j];
            }
    for(i=1;i<=a;i++)//行最高就是选该动物要变所有动物的最小花费
    {
        max=0;
        for(j=1;j<=a;j++)
        {
            if(max<c[i][j])
                max=c[i][j];
        }
        if(min>max)//比较选哪个动物咒语最短
        {
            n=i;
            min=max;
        }
    }
    if(min==INT)//如果min==TNT就说明无论选个动物都存在无法变的动物喽
        cout<<"0"<<endl;
    else
    cout<<n<<' '<<min<<endl;
}

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