Floyd算法

Floyd算法

December 1, 2019

1472views

411 words

#背景
程设作业题Week12-t1。给出一些单词，首尾字母形成首→尾的有向边，表明从首字母可以到达尾字母。问最后c能否到达d。
#分析
本题实际上是一个在给定图中寻找路径的题。此类问题的一般情况是每条边有一个权值，代表走这条边的花费，求某点到某点的最小花费。
#算法
可以用Floyd算法求解。也可以用Dijkstra算法求解，见：[Dijkstra算法][1]
Floyd算法（属于动态规划？）的思想为：
初始化：

- 初始化图（graph[][]数组）中的每一条边均为INF（“无穷大”值，代表不可到达）。
 - 初始化每个点到自己的权值为0。
 - 读入给定权值。

核心算法：

枚举中间点k(1-n)
        枚举起点i(1-n)
            枚举终点j(1-n)(可以加上j≠i)
                如果graph[i][j]<graph[i][k]+graph[k][j]
                    更新graph[i][j]为graph[i][k]+graph[k][j]

复杂度：O(n^3)。
其中最关键的思想在于最外层枚举的是中间点k。可以这样理解：

- 要找从i到j的花费比初始值小的路径，就是要找到通过一系列中转点k的路径i→k1→k2→...→j，这条路径的花费比当前花费更小。
 - 从1-n枚举中间点k，可以理解为，在枚举之前，不允许中转；
 - 枚举开始，首先允许通过k1（点1）中转，更新每两点之间的花费值；
 - 然后建立在通过k1中转的「基础」上，再允许通过k2（点2）中转，更新花费值……
 - 最后得到的就是允许通过任意一点中转的情况下，每两个点之间的最小花费值。

这里比较难理解的是该算法的枚举实现了通过枚举单个中转点实现了多个中转点。不严格地说，如果有路径i→k1→k2→...→j，枚举k1后就把i和k2直接相连，变成了i→k2→...→j；因此对于路径i→k1→k2→k3→...→j，再枚举k2时，**通过k1的中转已经“隐藏”在了i→k2中**；因此一步步枚举下去最后就是正确的。
该算法最终得到了任意两点之间的最短路径。
#代码实现
**注意点：**
初始化INF值时需保证2倍INF仍然在int范围内防止溢出。因为有中间过程`graph[i][k] + graph[k][j]`可能是两个INF相加。
使用memset初始化时，0x3e可以满足这一点。
本题是检查「连通性」，因此所有连通的边设为0即可。
    //
    //  main.cpp
    //  t1
    //
    //  Created by Colin on 2019/11/30.
    //  Copyright © 2019 Colin. All rights reserved.
    //
    #include <iostream>
    #include <fstream>
    #include <cstdio>
    #include <cmath>
    #include <string>
    #include <cstring>
    #include <cstdlib>
    using namespace std;
    
    const int MAXN = 30;
    const int inf = 1000000000;
    
    void shortest_path_Floyd(const int &n, int graph[MAXN][MAXN])
    {
        for (int k = 1; k <= n; k++)    //middle transfer point
        {
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (graph[i][j] > graph[i][k] + graph[k][j])
                        graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
    
    int main()
    {
        int graph[MAXN][MAXN] = { 0 };
        memset(graph, 0x3e, sizeof(graph));
        for (int i = 1; i <= MAXN - 1; i++)
            graph[i][i] = 0;
        string in;
        while (cin >> in)
        {
            int a = in[0] - 'a' + 1;
            int b = in[in.length() - 1] - 'a' + 1;
            graph[a][b] = 0;
        }
        shortest_path_Floyd('z' - 'a' + 1, graph);
        if (graph['c' - 'a' + 1]['d' - 'a' + 1] == 0)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    
        return 0;
    }

[1]: https://blog.valderfield.com/archives/8/

Last modification：December 1st, 2019 at 02:57 pm

如果觉得我的文章对你有用，请随意赞赏

Floyd算法