https://i.imgur.com/HSlAVh9.jpg
大家好，想請問這題藍框上答案的條件式
L(i,k,k-1)+L(k,j,k-1),if 1<=K<=n
為什麼會這樣寫？
根據L(i,j,k)的定義這樣的話可能會算到2k-2條邊？
我自己是寫
L(i,r,q)+L(r,j,k-q),if 1<=r<=n且0<=q<=k

這不就Floyd-Warshall的定義嗎...他上面連怎麼計算APSP都寫給你了

其實k的部分應該說成"最多可以走k-1個邊"的目前最佳解

...好蠢喔 所以Floyd warshall本來就有最多經過多少邊的意義在嗎

不對 應該說 L(i,j,k)= 只能走訪小於 k 的點的最佳但是因為 <k 所以自然就最多走 1~k 共 k-1個邊

我懂了 再請教一下bellman ford是不是也有一樣的意涵？

BF的話 就是根據"回合" 去 update第 n 回合，頂點只能往外走 n 步有一點不太一樣 (限制的條件)

我看懂了 題目是說經過的點 不是邊嗯嗯 是我完全沒看清楚題目 感謝m大e大