从疫情到求解最短路的Floyd算法

忽然间，还有两周多就要过年了。

不知是气温下降，还是临近春节人口流动较大，亦或是奥米克戎变种传播性强大，近期也是多出小疫情不断反弹。前文笔者还在考虑拜访亲朋是否可行，最近几周，深圳，也就是笔者所在的城市也出行了新冠感染。这导致一个问题：各地的防疫政策基本都要求中风险地区回乡需经历隔离。

不过万幸的是，本次疫情受到政府和人民的高度重视。迅速的控制住了局势，阻止了疫情的进一步传播。希望深圳在接下来的几周内能不断保持 0 新增，深圳稳住！

当然，本文会以此展开，从计算机的角度去做一些分析。

（本文讨论的疫情相关问题只为引申出算法知识，不含任何额外拓展含义。）

  关于前文信息可以点击连接查看游戏2048（C++版）

首先回顾一下图的存储，我们用的是最简单的方式——二维矩阵：

IsConnected数组只是单纯的用 0 和 1 来描述是否有边。如果说，我们不仅仅关心地点是否连通，还关心其他信息呢？

比如说，假如从 x 到 y 需要隔离 7 天， 从 y 到 z 又 需要隔离 7+7 天。而从 x 到 z 只需要 2+14 天。考虑到大家春节放假的时间不长，所以我们现在的问题就变成了——给出各地的防疫政策，求从 x 到 y 最少花费几天。

当然计算机处理现实问题一般需要将其做抽象，建立数学模型。

因此我们假设，在前文的基础上，给每条边设置一个权重，表示花费时间。现求一条从 x 到 y 路径，使得路径上边的权重之和最小，问这个最小值。其实这也就是算法中很经典的最短路问题。

那么很显然，IsConnected数组不能再单纯的只有 0 和 1 了，因为我们还有保留边的权重问题。接下来处理几个小问题：

1.边权如何表示？

答：将 IsConnected数组修改为 Cost数组。

2.怎么表示有边和无边？

答：有边则让 Cost数组有正常值，无边则将值修改为无穷大即可（计算机中无穷大一般用一个较大数字代替，比如 16 进制数字：0x3f3f3f3f）。

3.x 到 y 如果有多条边，每条边的权重不一，如何思考？

答：取最小边即可。因为最小的是最优方案，所以永远不会经过其他变。

所以边的处理如下：

ok，现在问题来到了最后一步，或者是终于回到了一开始的问题，如何求解最短路？

这边提供一种经典算法，Floyd算法。其本质是一个动态规划问题，如果讲述所占幅度较大，有些繁琐，具体原理这边不做过多解释，有兴趣的同学可以自己去网络查询。

那么做完这个看起来很繁琐的三重循环后，我们就可以直接求得任意两点之间的最小权重之和了。就存储在 Cost数组里。也就是说：

Cost数组现在是表达任意两点之间的最短距离。

那到这今天的问题就结束啦。各位也可以尝试一下这边的代码内容，来求解图上任意两点的最短路问题。当然前提是有一个合适的数学模型以及相应的数据，这方面可能就需要各位自己来总结和提炼了。