我在伊朗长大

动画里有一段女主每天看电视的场景，也不管电视放的啥，反正就是看。就跟刷抖音快手的人一个心态。我自己也被这种蜘蛛网抓住了，尽管不觉得这样很舒服，甚至垃圾信息过多搞得头疼，也不愿意停下来。写这些东西也是，头疼，其实也没那么疼。

以前看到一个视频，一个日本小哥天天送完外卖就呆旅馆看油管，三和大神一样。

根本原因是没人愿意朝200米高的篮筐投篮了吧。我在潜意识深处还是认为自己做的事并不能带来什么改变，对于变化我永远都只能当被动接受的一方，连主观能动性都被剥夺，跟死了没有区别。

啊对，我就烂，我就摆，我就是不如它们，这又怎么样呢？这也是演的啊，就像要跟Typec接口的手机交换数据，你就也得是个Typec接口，实际上你们JB谁啊，真的没兴趣，别再控制我的大脑了行吗？真是麻烦啊，真是麻烦死了，搞这些乱七八糟的。

我还真就是典型INTP，我觉得自己以前很外向，觉得我肯定是哪里病了，但仔细想想我的外向是怎么来的。是被强迫的，而且也没有多外向，只是跟谁都能聊两句所以朋友多而已。

那如果我真的是INTP，为什么我还需要社交？我不是可以从跟自己的对话中汲取能量吗？我没有这样的功能？我以前有，但是被剥夺了。

再怎么社交依旧感到孤独，交流也极度无聊，就用MBTI来解释，是因为我根本没办法从这些东西上汲取能量，这些东西没法内化为我的内驱力，又回到了那个问题——内驱力。

PTSD可能是一个原因，但其实没那么严重，不存在的东西有什么好怕的呢，只是我总觉得那玩意儿消失了我会......没有，自己吓自己真的无聊，一点都不帅，捞的淌口水真的。

我说说我真正在思考，真正觉得有意思的事吧：

我一直不明白为什么用队列在图上做BFS求最短路是对的，虽然无论用多少个例子去测试，都是正确的，动态调试也确实正确，但是到底为什么他喵的，他是正确的，我一直把这个问题压在心底。

但是昨天我问了Newbing以后，我明白了：

先假设点A到点B存在一条最短路C，这很重要，不要纠结点A到点B怎么就是最短路了，我们假设它是，那它就是，最初的数学也是这样的，就好像Bootloader一样，启动(构建)一个系统总要先有最基础的部分，但是已有知识为0的话，那个基础的部分就只能靠想象了，这就是想象力的重要性，因此不要再花时间质疑这一点了，只要它可以正常工作，那就是对的，最底层的东西背后没有本质，“造物主”肯定不懂数学，但不妨碍我们用数学解释世界，只要它可以工作就行了，别再TMD纠结这种最根本的东西了，求求了。有用=正确，仅限最底层的东西，因为有的时候你不把房子盖起来，是不知道房子可以盖多高的，而现在的房子已经捅破天了，即使有更好的底座，也已经不可能重建了，所以纠结这个真的没有意义，真没有.....

好，在认同这一点的基础上，往下想：

假如点A到点B没有中间点，那么C就是最短路；假如有，设这个点为X，那么就有AX，和XB两条路径。因为C已经确定是最短路了，别纠结，我说是就是，因此AX的长度+XB的长度一定是等于C的长度的，这也没有异议。那么如果C不是最短路，则AX或XB这两条路径里面，一定有一条更短的路径，即AX的长度+XB的长度<C的长度。

但是C我们已经假设过它是最短路了，而且它的长度也已经确定了，是等于AX+XB的。

然后精彩的地方来了，这里矛盾产生了，C不是最短路这个结论被我们在C是最短路下的前提下的某个推理推翻了......说实话，我从来没有这么想过。

我从来没有想过可以先假设一个结论是正确的，然后基于它去做各种推理，来反证它是对的。

这很......奇怪我说实话。先假设一件事正确，真的可以这样吗？你都假设它正确了，它能是不正确的吗？我的这个问题有点奇怪，但我确实一直被这种想法遮蔽着。

好吧，继续往下：

A到B之间C是最短路，这一点确定了。但是这跟BFS正确有什么关系呢？

刚刚的矛盾还能得出另一个结论：AB是最短路，则AX或XB也一定是最短路，因为把AX或XB换成一条更短的路径，会跟AX的长度+XB的长度=AB的长度这一点矛盾，因此AX或XB也是最短路。

换句话说，这个问题拥有最优子结构，子问题的解可以当作原问题的输入用。

你可以把AX跟XB再分成两半，直到最后变成最简单的情况，没有中间点。

然后因为队列总是会先访问离当前节点最近的节点，也就是没有中间点的情况，这种情况是最短路，这是确定的。然后继续往后访问，也都是这种没有中间点的最短路，因为这个问题有最优子结构，所以就像刚刚说的，AX最短，XB也最短，那么AB也将最短，因此从根节点开始队列往后延申的所有路径，都将是最短路。

更形象一点，有一个这样的无向图：

A-B-C

A首先加入队列，然后出队列，然后访问B。AB最短路确定，然后从B入列，出列，访问C，BC最短确定，因此AC最短也确定，如果AC不是最短，那么AB,BC中一定有一条更短的路，但是前面证明了这条路不存在。从C出发继续往后遍历，也都可以用这一套理论证明路径是最短的。

神了。我真的从来没有这么思考过，但是这样想以后瞬间理解了好多东西：就单单这一个问题，首先就有动态规划的思想，有数学归纳法，然后有BFS，能看出队列的性质。

原来这一切不是分散的，而是全部串联在一起的。之所以突然发现某道题会做了，是因为某块缺少的拼图后来找到了，因为一切都是紧密结合在一起的，这种结合就是创造的本质。

补充一点：按照上面的想法，其实你做DFS也能得出一样的结论，假如图变成这样：

A-B-C

   \/

就是AC之间直接连起来，那么DFS也是ABC的顺序，然后上面那一套证明ABC最短。

我要怎么证明DFS是错的呢？

不需要证明，因为第二层就已经得到AC的最短路径了，BFS下从B到C的路径是被封死的。

还是需要证明，这只能说明BFS为什么是对的，不能说明DFS为什么是错的。

那么还是先假设ABC是一条最短路，这样AB,BC也一定最短，这已经确定了。

不对，这个问题不在同一个层面：AB-BC最短，那么ABC肯定最短，这是对的。

但是这并不能说明这条路径就是A到C的最短路。

这真的需要证明吗？如果ABC是最短路，设它的长度为L，那么任何一条A通往C的路径长度都必须大于等于L，但是肉眼可见的，有一条路径的长度小于L，因此ABC不是最短路。

这样吧：假设DFS找到的路径是A到C之间存在的一条最短路P；再假设存在一个点D，也是C的邻接节点，并且跟A相连。这里别纠结为什么P不是ADC，就假设DFS找到的第一条路径是P，并且它是最短路。

此时得出结论：

1.ADC的长度>=P的长度

好，在这样前提下：设P的长度为10，但是ADC的长度为2，矛盾了，所以DFS找到的不是最短路。

不全对。其实DFS记录一下，还是可以用来找最短路的，只能证明DFS无法在第一次到达某个节点时，就经过了最短路径......

以前都是靠直觉理解的这些，完全没有一种可靠的感觉，就有一种随时有可能崩塌的感觉，所以做题做不出来，但是公式是绝对的，比直觉可靠，这条路才是对的。