先说很可能会讲错,这是自己看书慢慢理解的,并不挂保证 p.s 书是补习班讲义 洪捷 的 演算法-名校攻略秘笈 p.4-55 范例7 ※ 引述《mqazz1 (无法显示)》之铭言： Johnson的演算法那部分 有这个图 http://ppt.cc/1(V; 最左边的那个node是新加入的node 然後有一些问题 1. 如何及时发现，原graph有negative cycle ? 如果我回答，跑n次Bellman-Ford，发现有新的node被relaxtion，这样算及时吗 时间复杂度为 O(|V|) , 应该可以吧, 这题我无法明确回答你, 我也不知道及时的定义 2. 上面那个图，新加的一node造成新的graph，是否会产生新的negative cycle ? negative cycle 定义为 整个 cycle 路径总长为负值 而新加的点都指向其他点, 不要说负值了, 连cycle都没有 3. 上面那个图，新加的node作用是在做甚麽? 不加可以吗? 演算法是天才想的,天才说要加,就得加... Johnson's algo 的步骤如下 (节录 算法-名校攻略秘笈 p.4-56) 1. 加一个点 s，到其他点均有 edge，其上 weight 为 0。 (s均指向其他点,所以一定不会因为加s与其边产生cycle) 2.执行Bellman-Ford演算法， 若无负cycle，则记录每一点的h(v)为自s到v之shortest path 长。 3.对每一个edge做reweight如下： w'(u,v) = w(u,v)+h(u)-h(v)。 4.对每一个点执行Dijkstra's algotithm。 其实Johnson's algo重点就是在於reweight 让每个edge为正值，这样就绝对不会有negative cycle 而加node只是有个基准点吧 p.s 如果你有书,你可以参考 p.4-57 ex9, 用来解不等式, 感觉蛮方便的 -- 其实我是来赚P币的 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.168.66.93