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

shaowu459

题目要求如下图，除了截图中的信息简要补充说明如下：
1）AB列是航班出发地和目的地，出发地城市是1-15，每个出发地都有航班通往其他所有14个城市。
2）A列仅列示了部分航班信息，例如从城市1出发可以达到2~15这些城市，从城市2出发，列示了可以到达3~15这些城市，没有列示城市2到城市1的票价，因为这个票价和城市1到城市2票价一样。

shaowu459

由于AB列只列示了部分航班信息（往返不重复列示），为了方便筛选，我们调整下数据结构，保证从第一列筛选任意出发地，都能获得该出发地至其他城市的航班信息。
方法是将原数据第二列和第一列交换，然后堆积在原数据下方。

1. =LET(d,A2:C106,VSTACK(d,SORTBY(d,{1,0,2})))

复制代码

这样，我们在筛选某个城市作为出发地的时候，就能获得所有目的地和票价信息：

shaowu459

为了解决这个问题，我们设置如下的一个两列数组，第一列存储中转不超过k次到达左侧的目的地的最小花费，第二列存储对应的路径。


例如，F6单元格所在位置存储的就是在中转部超过k次时到达城市4的最小花费，右侧存储对应的路径。

shaowu459

后面分析以出发城市5，到达城市9，中转不超过k=5次为例说明解题思路。


首先，因为从城市5出发，所以在0次中转时候，也就是从城市5直接到达所有其他城市的花费如下（直接筛选出发地为5的结果）：



上图第1个红色方框表示，从城市5直接到城市1的最小花费是1336，因为是从城市5到的城市1，所以路径就记录“-5-”。
上图第2个红色方框表示，从城市5直接到城市8的最小花费是9157，因为是从城市5到的城市8，所以路径就记录“-5-”。
城市5自身保留0值，因为从城市5到城市5是不需要花费的。

shaowu459

前一步获得了中转k次，从城市5到所有其他城市的最小花费和路径。下面我们来分析当k=1的时候是什么情况。以城市6为例，首先我们筛选出从城市6出发到达所有其他城市的花费（一样的直接筛选即可）：


如下图红框中的数字，代表从城市6直接到城市12的花费：

shaowu459

继续分析，周转k=0次时，从城市5直接到城市6花费是5063，从城市5到其他城市花费也计算出来了。如果第一步从城市5到城市A（不等于6的城市）的花费+从城市A到城市6的花费要小于5063意味着什么？意味着有一个路径：城市5--->城市A--->城市6，经历了1次中转，并且花费更低。到底有没有呢，我们可以计算出城市6到每个城市的花费+第一步城市5到每个城市的花费来分析：


上图J列就是从城市5出发，经非城市6的城市中转，最终到城市6的所有花费。其中绿色部分的4027是J列的最小值，也就是从城市5出发经1次中转到城市6的最小花费。


4027的意思是：从城市5出发到城市12，然后从城市12到城市6的总花费是4027。从城市5出发经其他非城市12的城市再到城市6，花费都高于4027。

shaowu459

所以k=1时，到达城市6的最小花费就是4027（因为4027<5063，也就是比直接从城市5到城市6花费少），路径就是-5-12-6-（-6可以省略）。因此，存储最小花费和路径的数组就可以被更新，也就是k=0时城市6对应的绿色部分可以被更新成下图红框标注部分。

shaowu459

上面是以城市6为例，更新城市6对应的k=0到k=1的结果，同样，所有城市都可以逐个更新。



需要注意的是：
在更新过程中，城市A到城市A就不用更新了，可以设置成一个非常大的值，比如说4^8，不影响结果比较。另外，在更新时，例如城市6的路径已经有【-5-12-】了，也就是已经有城市5和城市12了，再更新的时候不再考虑从城市5或城市12出发的城市，也就是避免出现【-5-12-5-】这种路径，避免会出现返程的现象。

shaowu459

把每个城市都遍历一遍，更新k=0的数组，更新完毕后就变成了k=1，也就是中转一次时，从城市5出发到达每个城市的最小花费和路径。

例如下图中城市2的花费3824是从城市5到城市11，然后从城市11到城市2的花费，是经历1次中转从城市5到城市2的最小花费。同时，城市2对应的路径也从【-5-】更新为【-5-11-】


继续，循环生成k=2、3、4……时到达城市n的最小花费。当然，如果没有其他任何路径会比上一步的花费更少，那就保留上一步的结果不变，包括花费和路径都不变。例如，从城市5到城市2花费是1元，从城市5到所有其他城市都是几百几千元，因此无论k是几，从城市5到城市2的最小花费都是1元，在每次循环的时候都保持不变。

shaowu459

根据以上的分析，参考公式之一写法（循环方法，递归参见附件公式）如下。大体思路就是上面的分析思路，具体实现的时候公式稍有不同，仅供参考。

1. =LET(r,ROW(1:15),d,A2:C106,s,VSTACK(d,SORTBY(d,{1,0,2})),INDEX(REDUCE((r<>D2)*4^8&{"","-"},SEQUENCE(F2+1),LAMBDA(x,y,LET(钱,TAKE(x,,1),路,DROP(x,,1),临,REDUCE(钱,r,LAMBDA(m,n,HSTACK(m,IF(ISERR(FIND(-r&"-",INDEX(路,n))),IFNA(VLOOKUP(r,FILTER(s,INDEX(s,,2)=n),3,)+INDEX(钱,n),""))))),k,BYROW(临,LAMBDA(z,MATCH(MIN(z),z,)-1)),HSTACK(BYROW(临,MIN),IF(k,INDEX(路,k)&k&"-",路))))),E2,1))

复制代码