今天想跟大家伙儿聊聊我捣鼓“弗洛”这玩意儿的经历。我是碰上个麻烦事儿，手头有好些个点，互相之间有的连着有的不连着，连着的，还有个距离或者说代价。我就寻思，咋能知道从任意一个点到另外任意一个点，最短得走多远？
起初的念头和碰壁
最开始我想的简单，就想着一个点一个点地算。比如，从A点出发，到B点多远，到C点多远…… 这法子，点少还行，点一多，或者说我想知道所有点对之间的最短距离，那就麻烦了，得一个一个来，算到猴年马月去。也想过用那个啥“迪杰斯特拉”，那玩意儿是一个点到其他所有点的，也挺好用，但我要的是所有点到所有点，用它的话就得每个点都当起点跑一遍，感觉还是有点繁琐。
偶然想起“弗洛”
后来我就琢磨，有没有更省事儿的法子？翻了翻以前的笔记，加上在网上瞎搜搜，就看到了这个“弗洛”算法。一看介绍，这不正是我想要的嘛它就能一次性把所有点到所有点的最短路径都给算出来。
我是怎么一步步理解和实践的
这“弗洛”算法，我一开始看那些公式化的东西，也是有点懵。后来我换了个思路琢磨，它的核心思想挺巧妙的，我给它起了个外号叫“中转站大法”。
我的实践步骤大概是这样的：
- 准备工作：画个图，填个表。 我先弄了个类似表格的东西，行和列都代表那些点。表格里的数字，就代表两个点之间的直接距离。比如A到B直接连着，距离是5，那就在A行B列（还有B行A列）填上5。如果A到C不直接连，我就先填个特大特大的数，意思就是暂时过不去。自己到自己，那肯定是0嘛这个表，他们管叫“邻接矩阵”，我听着也挺形象。
- 找“中转站”：挨个点来当“跳板”。 这是最关键的一步。我想，从点i到点j，不一定非得直着走，是不是可以经过某个中转点k，让路程更短？比如说，从北京到广州，直接飞可能不如先飞到武汉，再从武汉飞到广州来得便宜（这里只是打比方，实际情况不一定）。
- 套圈儿比较：三层循环是标配。 我就设了三层循环。最外头那一层，就是挨个尝试让每个点都来当一次那个“中转站k”。里头两层，就是遍历所有的起点i和终点j。
- 更新路径：取更短的。 在循环里头，我就比较：从i直接到j的距离，跟“从i先到中转站k，再从中转站k到j”的距离之和，哪个更短？如果经过中转站k更短，那我就把表格里i到j的距离更新成这个更短的值。我当时就想，distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])，这句话真是精髓！
捣鼓过程中的小发现
刚开始的时候，我把那个“不直接连通”的距离设得不够大，结果有时候算着算着就出错了，因为它错误地以为某条“不通的路”反而是“近路”。后来我学乖了，直接用个程序里能表示的最大的数，或者干脆就标记成“无穷大”，这样就好多了。
还有就是那个循环的顺序，我一开始还担心k、i、j这三个的嵌套顺序会不会影响结果。后来试了试，也查了查，发现只要保证最外层是那个“中转站”k，里头两层i和j的顺序关系不大，结果都是对的。这点还挺有意思。
成了！
就这么着，让程序把所有的点都当过一遍“中转站”，把所有的起点终点都比较过一遍之后，我那个初始的“邻接矩阵”表格，就神奇地变成了存着所有点对之间最短路径的表了！
比如，一开始A到C不通，是无穷大。但如果A到B是5，B到C是3，那么当B作为中转站k的时候，程序就会发现A到C可以通过B走，距离是5+3=8，比无穷大小，就把A到C的距离更新成8了。
整个过程下来，感觉“弗洛”这法子虽然看着简单粗暴，三层循环嘛但确实有效，而且理解起来也还算直观。对于我这种需要知道任意两点间最短距离的场景，真是帮了大忙。分享给大家，希望对你们也有点启发！
还没有评论，来说两句吧...