作者mistel (Mistel)
看板Grad-ProbAsk
標題[理工] 演算法 圖論
時間Wed Nov 13 00:08:57 2019
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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.152.255 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1573574939.A.C81.html
1F：→ mathtsai: 這不就Floyd-Warshall的定義嗎... 11/13 00:49
2F：→ mathtsai: 他上面連怎麼計算APSP都寫給你了 11/13 00:50
3F：→ ekids1234: 其實k的部分應該說成"最多可以走k-1個邊"的目前最佳解 11/13 00:53
4F：→ mistel: ...好蠢喔 所以Floyd warshall本來就有最多經過多少邊的 11/13 00:56
5F：→ mistel: 意義在嗎 11/13 00:56
6F：→ ekids1234: 不對 應該說 L(i,j,k)= 只能走訪小於 k 的點的最佳 11/13 00:57
7F：→ ekids1234: 但是因為 <k 所以自然就最多走 1~k 共 k-1個邊 11/13 00:57
8F：→ mistel: 我懂了 再請教一下bellman ford是不是也有一樣的意涵？ 11/13 01:00
9F：→ ekids1234: BF的話 就是根據"回合" 去 update 11/13 01:04
10F：→ ekids1234: 第 n 回合，頂點只能往外走 n 步 11/13 01:05
11F：→ ekids1234: 有一點不太一樣 (限制的條件) 11/13 01:05
12F：→ mistel: 我看懂了 題目是說經過的點 不是邊 11/13 01:06
13F：→ mistel: 嗯嗯 是我完全沒看清楚題目 感謝m大e大 11/13 01:07