Floyd深度解析

应用范围

$\space\space$Floyd是唯一的多源最短路算法 用领接矩阵存储 可以处理负边权 但不能处理负环 多源最短路就是说只要跑一次 任意两点的最短路都能求得 而其他单源最短路跑一次只能得出一个点到其他点的最短路

由于有三重循环 每层都是n次 时间复杂度为O($n^3$) 虽然在稠密图中优势明显 但是对于稀疏图则占不到一点便宜 是一个优雅暴力的算法

初始化

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            if(i == j) g[i][j] = 0;
            else g[i][j] = INF;
        }
    }

核心代码

void floyd()
{
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

拓展：探寻Floyd的本质

我们先看这道题目 灾后重建
由 上一章 讲到 Floyd本质是个DP问题

故而 我们需要仔细探索下DP的含义 首先 我们的第一层循环K代表着状态 即在通过节点编号不超过k的点来进行从i->j的转移 进而求最短路 实际上 Floyd最本质的思想 就是利用其他的点进行中转 从而达到求出最短路的目的

我们在看下核心代码

void floyd()
{
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

这段代码的基本思想就是：最开始只允许经过1号顶点进行中转 接下来只允许经过1号和2号顶点进行中转......允许经过1 ~ n号所有顶点进行中转 求任意两点之间的最短路程 用一句话概括就是 所有从i号出发 最终走到到j 且只经过节点编号不超过k的最短路程

到这里我们已经知道 Floyd是一个利用其他点进行中转来求最短路的步骤
而此时我们再回头看题意：
所有的边全部给出 按照时间顺序更新每一个可用的点(即修好村庄) 对于每个时间点进行两点之间的询问 求对于目前建设的所有村庄来说任意两点之间的最短路
不正好就是Floyd算法中使用前k个节点更新最短路的思维吗？并且 我们是如何枚举k个节点的 是陆续进行枚举 不就是题意中“按照时间顺序更新每一个可用的点吗”

于是到此 我们也差不多知道了本题的写法

算法设计

1. 读入 村下每个村庄修复的时间
2. 读入所有边并使用领接矩阵存图
3. 初始化
4. 对于每次询问 将在当前时间前的所有点用Floyd更新
5. 特殊判断并输出

源码

#include<iostream>
using namespace std;

const int N = 210, INF = 1e9;

int n, m, k;
int cost[N];
int g[N][N], test;

void floyd(int k)
{
    for(int i = 0; i < n; i ++)
       for(int j = 0; j < n; j ++)
          if(g[i][j] > g[i][k] + g[k][j])
              g[i][j] = g[j][i] = g[i][k] + g[k][j];
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> cost[i];

    for(int i = 0; i < n; i ++) //初始化
       for(int j = 0; j < n; j ++)
         if(i == j) g[i][j] = 0;
         else g[i][j] = INF;

    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);//无向图存储
    }

    cin >> test;
    int k = 0;
    while(test --)
    {
        int x, y, t;
        cin >> x >> y >> t;
        while(cost[k] <= t && k < n) //在给定的时间内能完成的节点数
        {
            floyd(k);
            k ++;
        }
        //判断输出
        if(cost[x] > t || cost[y] > t || g[x][y] > INF / 2) cout <<"-1" <<endl;
        else
        cout << g[x][y] <<endl;
    }

    return 0;
}