[理工] 演算法 圖論

看板Grad-ProbAsk作者 (Mistel)時間4年前 (2019/11/13 00:08), 編輯推噓0(0推 0噓 13→)
留言13則, 3人參與, 4年前最新討論串3/3 (看更多)
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1573574939.A.C81.html
→
11/13 00:49, 4年前 , 1F
這不就Floyd-Warshall的定義嗎...
11/13 00:49, 1F
→
11/13 00:50, 4年前 , 2F
他上面連怎麼計算APSP都寫給你了
11/13 00:50, 2F
→
11/13 00:53, 4年前 , 3F
其實k的部分應該說成"最多可以走k-1個邊"的目前最佳解
11/13 00:53, 3F
→
11/13 00:56, 4年前 , 4F
...好蠢喔 所以Floyd warshall本來就有最多經過多少邊的
11/13 00:56, 4F
→
11/13 00:56, 4年前 , 5F
意義在嗎
11/13 00:56, 5F
→
11/13 00:57, 4年前 , 6F
不對 應該說 L(i,j,k)= 只能走訪小於 k 的點的最佳
11/13 00:57, 6F
→
11/13 00:57, 4年前 , 7F
但是因為 <k 所以自然就最多走 1~k 共 k-1個邊
11/13 00:57, 7F
→
11/13 01:00, 4年前 , 8F
我懂了 再請教一下bellman ford是不是也有一樣的意涵？
11/13 01:00, 8F
→
11/13 01:04, 4年前 , 9F
BF的話 就是根據"回合" 去 update
11/13 01:04, 9F
→
11/13 01:05, 4年前 , 10F
第 n 回合，頂點只能往外走 n 步
11/13 01:05, 10F
→
11/13 01:05, 4年前 , 11F
有一點不太一樣 (限制的條件)
11/13 01:05, 11F
→
11/13 01:06, 4年前 , 12F
我看懂了 題目是說經過的點 不是邊
11/13 01:06, 12F
→
11/13 01:07, 4年前 , 13F
嗯嗯 是我完全沒看清楚題目 感謝m大e大
11/13 01:07, 13F
‣ 更多 mistel 的文章
文章代碼(AID): #1TojaRo1 (Grad-ProbAsk)
‣ 更多 mistel 的文章
文章代碼(AID): #1TojaRo1 (Grad-ProbAsk)