K站中转内最便宜的航班总花费

shaowu459

上面的循环公式，把Index函数去掉，结果就是一个15行2列的数组，因为要到城市9，所以提取数组中的低9行元素即可。




如果只要最小花费就INDEX(数组,9,1)，如果连着路径，可以直接去掉INDEX函数的第三参数INDEX(数组,9)。

夜雨无声1949

shaowu459 发表于 2024-8-24 20:58
上面的循环公式，把Index函数去掉，结果就是一个15行2列的数组，因为要到城市9，所以提取数组中的低9行元素 ...

虽然看不懂，不过老师真有耐心，送上小花。

edwin11891

思路是明白了，要是我按照这个思路写公式，估计火车长度还得翻倍！

shaowu459

edwin11891 发表于 2024-8-24 22:00
思路是明白了，要是我按照这个思路写公式，估计火车长度还得翻倍！

还有其他思路的，写法也不少。可以独立尝试写写

皮蛋solo周

借超人老师的帖子简单说下bellman ford算法，粗浅理解，大家去伪存真

贝尔曼-福特算法（Bellman-Ford Algorithm）用于在加权有向图中找到从源点到其他所有顶点的最短路径。在求有限制条件的最短路径时非常直观，实现简单易懂，就是时间复杂度较高O(V×E), 其中 VV是顶点的数量，EE是边的数量。

贝尔曼-福特算法的工作原理
贝尔曼-福特算法的核心思想是通过松弛（Relaxation）操作来逐步逼近最短路径。具体步骤如下：

初始化:
对于所有的顶点，将源点到每个顶点的距离初始化为“正无穷”（excel中用较大值9^9代替），源点到自身的距离初始化为0。

如上图7*15的二维数组，7行代表k+2（比k多出的两行，一行是需要设置初始值，另一行是记录中转次数k=0的价格），15列依次代表这15个城市，初始化为0的单元格这一列代表出发城市src 13

松弛边缘:
对数组中的每一行的每一列，尝试通过源点路径更新目的地节点的价格。如果通过这列可以使得目的地节点的价格变得更低，则更新该节点的最低路径价格。因为我们需要对每一行的每一列进行更新，所以需要使用双层嵌套reduce函数，外层从2开始到7共循环k+1行（第一行不用更新），内层循环PERMUT(15,2)=210次取到每个城市航班对应的信息，使用makearray来判断当前行列值是否相等（返回逻辑值进行批量填表），更新最新价格

第一次循环y=2，就更新x中第二行的值（makearray中r=y），然后内层循环每次取出对应城市的始发站、终点站和价格，依次对应（makearray中s=i）价格与上一行（y-1）比较取最小值MIN(INDEX(m,y,i),INDEX(m,y-1,INDEX(a,n,1))+INDEX(a,n,3))，不等于y的行就保持m不变，当第一次y=2外层循环结束后，这一行代表的就是从13出发到每一个城市中转0次的最低价格。以此类推得到中转1至5次的最低价格，最后iindex取出对应的目的地dst的列，取最小值即为最多中转5次的最低价格。

附件与超人老师提供的一致，部分内容来自网络，公式参考了力扣官方题解python的写法

完整公式：
=LET(a,VSTACK(A2:C106,HSTACK(B2:B106,A2:A106,C2:C106)),MIN(INDEX(REDUCE(IF(SEQUENCE(F2+2,15)=D2,,9^9),SEQUENCE(F2+1)+1,LAMBDA(x,y,REDUCE(x,SEQUENCE(210),LAMBDA(m,n,LET(i,INDEX(a,n,2),IF(MAKEARRAY(F2+2,15,LAMBDA(r,s,(r=y)*(s=i))),MIN(INDEX(m,y,i),INDEX(m,y-1,INDEX(a,n,1))+INDEX(a,n,3)),m)))))),,E2)))

包括路径的公式
=LET(a,VSTACK(A2:C106,HSTACK(B2:B106,A2:A106,C2:C106)),b,INDEX(REDUCE(IF(SEQUENCE(F2+2,15)=D2,,9^9),SEQUENCE(F2+1)+1,LAMBDA(x,y,REDUCE(x,SEQUENCE(210),LAMBDA(m,n,LET(i,INDEX(a,n,2),j,INDEX(a,n,1),k,INDEX(m,y,i),t,TEXTSPLIT(INDEX(m,y-1,j),"-"),u,INDEX(a,n,3),q,j&"(¥"&u&")",o,@t+u,p,IF(y>2,TAKE(t,,-1)&"→"&q,q),IF(MAKEARRAY(F2+2,15,LAMBDA(r,s,(r=y)*(s=i))),IF(--@TEXTSPLIT(k,"-")>o,o&"-"&p,k),m)))))),,E2),TEXTSPLIT(@SORTBY(b&"→"&E2,--TEXTSPLIT(b,"-")),"-"))