作者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/cn.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